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)
这道题不难,只是以前路径记录没有掌握好,水一水
#include<stdio.h> #include<string.h> #include<queue> #include<stack> #include<algorithm> using namespace std; #define MAX 10 int map[MAX][MAX]; bool vis[MAX][MAX]; int dx[4]={1,-1,0,0}; int dy[4]={0,0,-1,1}; struct node { int x,y,prex,prey; }; node path[MAX][MAX]; node st,ed; void putpath(int x,int y) { stack<node>p; node now=path[x][y]; while(1) { p.push(now); if(now.x==0&&now.y==0) break; now=path[now.prex][now.prey]; } while(!p.empty()) { now=p.top(); p.pop(); printf("(%d, %d) ",now.x,now.y); } } bool check(node a) { if(map[a.x][a.y]==1||a.x<0||a.y>4||a.y<0||a.x>4) return 0; return 1; } void bfs() { memset(vis,0,sizeof(vis)); queue<node>q; st.x=0,st.y=0; q.push(st); vis[0][0]=1; while(!q.empty()) { st=q.front(); q.pop(); if(st.x==4&&st.y==4) { path[st.x][st.y]=st; break; } for(int i=0;i<4;i++) { ed.x=st.x+dx[i]; ed.y=st.y+dy[i]; if(check(ed)&&!vis[ed.x][ed.y]) { vis[ed.x][ed.y]=1; ed.prex=st.x; ed.prey=st.y; path[ed.x][ed.y]=ed; q.push(ed); } } } } int main() { for(int i=0;i<5;i++) { for(int j=0;j<5;j++) scanf("%d",&map[i][j]); } bfs(); putpath(4,4); return 0; }