//
// main.cpp
// hdu1260
//
// Created by Haoying Zhao on 17/9/6.
// Copyright ? 2017年 Haoying Zhao. All rights reserved.
//
#include <iostream>
#include <limits.h>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
using namespace std;
struct point {
int x, y;
};
int a[6][6];
bool mark[6][6];
int pre[26];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
point que[26];
void print_point(int t) {
if(pre[t] == -1) {
printf("(%d, %d)\n",que[t].x,que[t].y);
return;
}
print_point(pre[t]);
printf("(%d, %d)\n",que[t].x,que[t].y);
}
int bfs(point s, point e) {
memset(pre, -1, sizeof(pre));
memset(mark, false, sizeof(mark));
memset(que, 0, sizeof(que));
int head = 0, tail = 1;
que[head] = s;
mark[s.x][s.y] = 1;
while(head != tail) {
for(int i = 0; i < 4; ++i) {
int xx = que[head].x + dx[i];
int yy = que[head].y + dy[i];
if(xx < 0 || yy < 0 || xx >= 5 || yy >= 5 || mark[xx][yy] == 1 || a[xx][yy] == 1)
continue;
point t;
t.x = xx;
t.y = yy;
que[tail] = t;
pre[tail] = head;
mark[xx][yy] = 1;
if(xx == 4 && yy == 4) {
print_point(tail);
return true;
}
tail++;
}
head++;
}
return false;
}
int main() {
for(int i = 0; i < 5; ++i)
for(int j = 0; j < 5; ++j)
cin >> a[i][j];
point a,b;
a.x = a.y = 0;
b.x = b.y = 4;
bfs(a,b);
return 0;
}
20170907_poj3984
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門(mén)都伪，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)呕乎，“玉大人，你說(shuō)我怎么就攤上這事陨晶♀剩” “怎么了？”我有些...
- 文/不壞的土叔 我叫張陵先誉，是天一觀的道長(zhǎng)湿刽。 經(jīng)常有香客問(wèn)我，道長(zhǎng)褐耳，這世上最難降的妖魔是什么诈闺？ 我笑而不...
- 正文 為了忘掉前任，我火速辦了婚禮铃芦，結(jié)果婚禮上买雾，老公的妹妹穿的比我還像新娘。我一直安慰自己杨帽，他們只是感情好，可當(dāng)我...
- 文/花漫 我一把揭開(kāi)白布嗤军。 她就那樣靜靜地躺著注盈，像睡著了一般。 火紅的嫁衣襯著肌膚如雪叙赚。 梳的紋絲不亂的頭發(fā)上老客，一...
- 那天僚饭，我揣著相機(jī)與錄音，去河邊找鬼胧砰。 笑死鳍鸵，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的尉间。 我是一名探鬼主播偿乖，決...
- 文/蒼蘭香墨 我猛地睜開(kāi)眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼哲嘲！你這毒婦竟也來(lái)了贪薪？” 一聲冷哼從身側(cè)響起，我...
- 序言：老撾萬(wàn)榮一對(duì)情侶失蹤眠副，失蹤者是張志新（化名）和其女友劉穎画切，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體囱怕，經(jīng)...
- 正文 獨(dú)居荒郊野嶺守林人離奇死亡霍弹，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
- 正文 我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了娃弓。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片典格。...
- 正文 年R本政府宣布私恬，位于F島的核電站，受9級(jí)特大地震影響炼吴，放射性物質(zhì)發(fā)生泄漏本鸣。R本人自食惡果不足惜，卻給世界環(huán)境...
- 文/蒙蒙 一硅蹦、第九天 我趴在偏房一處隱蔽的房頂上張望荣德。 院中可真熱鬧，春花似錦童芹、人聲如沸涮瞻。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)署咽。三九已至，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間宁否，已是汗流浹背窒升。 一陣腳步聲響...
- 正文 我出身青樓，卻偏偏與公主長(zhǎng)得像台谊，于是被迫代替她去往敵國(guó)和親蓉媳。 傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
推薦閱讀更多精彩內(nèi)容
- 姓名:冉喬琪~公司:天興醫(yī)藥 【日精進(jìn)打卡第※88※天】 【知～學(xué)習(xí)】 《六項(xiàng)精進(jìn)》2遍 共292遍 《大學(xué)》2遍...
- 氣質(zhì)是什么青伤？像大家都熟知的主持人董卿督怜，電視劇《我的前半生》里的唐晶，她們說(shuō)話做事特別干練狠角，衣服的著裝也讓人看著舒服...
- 兒童金錢(qián)觀培養(yǎng) 一号杠、讓孩子知道錢(qián)是哪來(lái)的； 我們應(yīng)該盡早讓孩子知道：金錢(qián)是通過(guò)辛苦工作換來(lái)的丰歌，是付出勞動(dòng)后的報(bào)酬姨蟋。...
- 到了現(xiàn)在我發(fā)現(xiàn)現(xiàn)在最難的不是去學(xué)習(xí)什么，而是下決心去學(xué)習(xí)什么立帖，這也是我沒(méi)有很好的提升我的執(zhí)行力的原因之一眼溶。其實(shí)我應(yīng)...
