首页 > 代码库 > POJ 3984:迷宫问题(BFS+路径记录)
POJ 3984:迷宫问题(BFS+路径记录)
迷宫问题
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 7560 | Accepted: 4426 |
Description
定义一个二维数组:
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。
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)
题意。。题目已经告诉你了。。
就是用搜索记录路径就行。。
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<queue> #include<cmath> using namespace std; int map[6][6]; int dx[] = {-1, 0, 0, 1}; int dy[] = {0, -1, 1, 0}; int pre[30]; struct node { int x; int y; }; node path[30]; void output(int head) { int tmp = pre[head]; if(tmp==0) printf("(%d, %d)\n", path[tmp].x, path[tmp].y); else output(tmp); printf("(%d, %d)\n", path[head].x, path[head].y); } void bfs() { int head = 0; int tail = 1; pre[head] = -1; path[head].x = 0; path[head].y = 0; map[ path[head].x][path[head].y ] = 1; while(head<tail) { int x = path[head].x; int y = path[head].y; if(x==4 && y==4) { output(head); return ; } for(int i=0;i<4;i++) { int xx = x + dx[i]; int yy = y + dy[i]; if(map[xx][yy]==0 && xx>=0 && xx<5 && yy>=0 && yy<5 ) { map[xx][yy]=1; path[tail].x = xx; path[tail].y = yy; pre[tail] = head; tail++; } } head++; } } int main() { int i,j; for(i=0;i<5;i++) for(j=0;j<5;j++) scanf("%d",&map[i][j]); bfs(); return 0; }
还有一种写法。。不过是别人的。。。Orz。。。
#include<iostream> #include<queue> using namespace std; int a[5][5]; int dir[4][2]= {0,1,1,0,-1,0,0,-1}; int map[5][5]; void bfs(int x,int y) { queue<int> q; q.push(x); q.push(y); while(!q.empty()) { int m=q.front(); q.pop(); int n=q.front(); q.pop(); for(int i=0; i<4; i++) { int mm=m+dir[i][1]; int nn=n+dir[i][0]; if(mm==4 && nn==4) { map[mm][nn]=m*5+n; return ; } if(mm>=0 && mm<=4 && nn>=0 && nn<=4 && a[mm][nn]!=1) { q.push(mm); q.push(nn); map[mm][nn]=(5*m+n);//计算路径的好方法 a[mm][nn]=1; } } } } void print(int i,int j) { if(i==0&&j==0) { printf("(0, 0)/n"); return ; } print(map[i][j]/5,map[i][j]%5); printf("(%d, %d)/n",i,j); } int main() { for(int i=0; i<5; i++) { for(int j=0; j<5; j++) { cin>>a[i][j]; } } bfs(0,0); print(4,4); return 0; }
POJ 3984:迷宫问题(BFS+路径记录)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。