POJ 3984 迷宫问题 【bfs】【路径打印】
迷宫问题
Description
定义一个二维数组:
int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, };
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组,表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径,格式如样例所示。
Sample Input
0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0
Sample Output
(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4)
Source
这题输出有坑,注意逗号后面有一个空格。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> #include<map> #include<queue> using namespace std; #define LL long long #define M(a,b) memset(a,b,sizeof(a)) const int MAXN = 1e3+5; const int INF = 0x3f3f3f3f; int X[5] = {0,1,-1,0,0}; int Y[5] = {0,0,0,1,-1}; int MAP[10][10]; int vis[10][10]; int len; struct Node { int x,y; int from;///记录上一步的下标 } Path[MAXN]; queue<pair<pair<int,int>, int> >q; int bfs(int x,int y) { vis[x][y] = 1; q.push(make_pair(make_pair(x,y),len)); while(!q.empty()) { int x1 = q.front().first.first; int y1 = q.front().first.second; int temp = q.front().second; if(x1==5&&y1==5) { return len; } q.pop(); for(int i=1; i<=4; i++) { int xx = x1+X[i]; int yy = y1+Y[i]; if(xx>=1&&xx<=5&&yy>=1&&yy<=5&&vis[xx][yy]==0&&MAP[xx][yy]==0) { len++; Path[len].x = xx; Path[len].y = yy; Path[len].from = temp; vis[xx][yy] = 1; q.push(make_pair(make_pair(xx,yy),len)); } } } } void pri(int s) { int temp = s; int num[MAXN]; int len2 = 0; num[len2++] = s; while(Path[temp].from!=0) { num[len2++] = Path[temp].from; temp = Path[temp].from; } printf("(0, 0) "); for(int i=len2-1; i>=0; i--) { printf("(%d, %d) ",Path[num[i]].x-1,Path[num[i]].y-1); } } void init() { M(vis,0); len = 0; Path[len].from = 0; while(!q.empty()) q.pop(); } int main() { while(~scanf("%d",&MAP[1][1])) { init(); for(int i=2; i<=5; i++) { scanf("%d",&MAP[1][i]); } for(int i=2; i<=5; i++) { for(int j=1; j<=5; j++) { scanf("%d",&MAP[i][j]); } } int ans = bfs(1,1); pri(ans); } return 0; }
下一篇:
字节青训营课程一——html