定义一个二维数组： 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， 输出路劲的时候用dfs
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> using namespace std; int n,m,ans; const int N = 11; int vis[N][N]; int a[N][N]; int f[111]; int dx[]={-1,0,1,0}; int dy[]={0,1,0,-1}; struct P { int x,y,step; P(int x,int y,int step):x(x),y(y),step(step){} }; int bfs() { int i,j,rt,son; queue<P>que; que.push(P(1,1,0)); vis[1][1]=1; while(!que.empty()) { P p = que.front(); rt = (p.x-1)*5+p.y; if(p.x==5 && p.y==5) return p.step; que.pop(); for(i=0;i<4;i++) { int tx = p.x + dx[i]; int ty = p.y + dy[i]; if(tx<1||ty<1||tx>5||ty>5||a[tx][ty]==1) continue; if(vis[tx][ty]) continue; vis[tx][ty]=1; son = (tx-1)*5+ty; f[son]=rt; que.push(P(tx,ty,p.step+1)); } } } void print(int num) { int x,y; if(num!=1) print(f[num]); x=num/5; if(num%5) x++; y=num%5; if(y==0) y=5; printf("(%d, %d)\n",x-1,y-1); return; } int main() { int i,j; for(i=1;i<=5;i++) for(j=1;j<=5;j++) scanf("%d",&a[i][j]); bfs(); print(25); }
