NowCoder最喜欢游乐场的迷宫游戏，他和小伙伴们比赛谁先走出迷宫。 现在把迷宫的地图给你，你能帮他算出最快走出迷宫需要多少步吗？ 输入描述: 输入包含多组数据。每组数据包含一个10*10，由“#”和“.”组成的迷宫。其中“#”代表墙；“.”代表通路。入口在第一行第二列；出口在最后一行第九列。从任意一个“.”点都能一步走到上下左右四个方向的“.”点。 输出描述: 对应每组数据，输出从入口到出口最短需要几步。 输入例子: #.#########........##........##........##........##........##........##........##........#########.##.#########........#########.##........##.#########........#########.##........##.######.#########.# 输出例子: 1630
也是一个经典的bfs问题.给定了起点和终点,直接搜就行。
// write your code here cpp
#include
#include
#include
using namespace std;
char mp[25][25];
int sx,sy,maxn;
int dir[4][2]={-1,0,1,0,0,-1,0,1};
struct point {
int x,y,step;
};
int bfs() {
queue
point s;
s.x=0;s.y=1;s.step=0;
que.push(s);
mp[s.x][s.y]='#';
while(!que.empty()) {
point e=que.front();
que.pop();
if(e.x==9&&e.y==8) return e.step;
for(int i=0;i<4;++i) {
s.x=e.x+dir[i][0];
s.y=e.y+dir[i][1];
if(s.x>=0&&s.x<10&&s.y>=0&&s.y<10&&mp[s.x][s.y]!='#')
{
s.step=e.step+1;
mp[s.x][s.y]='#';
que.push(s);
}
}
}
return -1;
}
int main() {
while(~scanf("%s",mp[0])) {
for(int i=1;i<10;++i) {
scanf("%s",mp[i]);
}
printf("%d\n",bfs());
}
return 0;
}
