Time Limit: 1000MS | Memory Limit: 65536KB | 64bit IO Format: %I64d & %I64u |
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) 分析:首先用BFS,遍历迷宫,找到最短路径,并且遍历过程中,标记走过的点。遍历完成后,从终点回到 起点,因为有人走过从起点走到过终点,那么一定可以从终点回到,起点这也就是寻找走过路径的最好理 解方式。
#include<queue> #include<string.h> #include<stdio.h> using namespace std; struct Point { int i; int j; }; Point path[50]; Point p; queue<Point>q; int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; int visit[10][10]; int main( ) { int road[6][6],i,j,k,xx,yy,a,b,len=0; memset(visit,0,sizeof(visit)); for(i=0;i<5;i++){ for(j=0;j<5;j++){ scanf("%d",&road[i][j]); } } p.i=0; p.j=0; q.push(p); visit[0][0]=1; while(!q.empty()) { p=q.front(); q.pop(); for(i=0;i<4;i++) { xx=p.i+dir[i][0]; yy=p.j+dir[i][1]; if(xx<0||xx>4||yy<0||yy>4)continue; if(road[xx][yy]==0&&!visit[xx][yy]) { visit[xx][yy]=visit[p.i][p.j]+1; if(xx==4&&yy==4) { len=visit[xx][yy]; break; } Point newP; newP.i=xx; newP.j=yy; q.push(newP); } } } p.i=4,p.j=4; for(i=len-1;i>=0;i--) { path[i].i=p.i; path[i].j=p.j; for(j=0;j<4;j++) { xx=p.i+dir[j][0]; yy=p.j+dir[j][1]; if(xx<0||xx>4||yy<0||yy>4)continue; if((visit[xx][yy]==visit[p.i][p.j]-1)) { p.i=xx; p.j=yy; break; } } } for(i=0;i<len;i++) printf("(%d, %d)\n",path[i].i,path[i].j); return 0; }
相关推荐
算法入门—广度优先搜索—raphealguo
想看看自己的编程能力到底怎么样,很多人都回去做一做POJ的题目吧,在这里你不妨可以先看看它的题目分析。
POJ1321棋盘问题 很好两种解法很值得去参考一下 完整的实验报告还有代码希望kan
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
放炮问题,北大网站 POJ 1185 算法
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
POJ1048,加强版的约瑟夫问题 难度中等
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
北大POJ1004-Financial Management 解题报告+AC代码
北大poj1012-Joseph【经典约瑟夫问题】 poj1012-Joseph【经典约瑟夫问题】
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ 1328 java做!雷达问题!java版本!AC答案~
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
百练POJ1088滑雪问题的源代码,C写的,不过后缀是.cpp。写的还算比较易懂,呵呵