迷宫问题 POJ--3984

迷宫问题 Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 21696 Accepted: 12698

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 <cstring> #include <algorithm> #include <iostream> #include <stdio.h> using namespace std; int maze[6][6]; int vis[6][6],temp[61][2]; int ans[61][2]; int o,p,mi=666666666; void dfs(int x,int y,int step) { int tx,ty,k;int next[4][2]={{0,1},{1,0},{-1,0},{0,-1}}; //迷之错在了二维数组的定义初始化上 if(x==4 && y==4) { if(step<mi) //满足便重新存 { mi=step; for(int i=0; i < mi; i++) { ans[i][0]=temp[i][0]; ans[i][1]=temp[i][1]; } } return ; } for(k=0;k <= 3;k++) { tx=x+next[k][0]; ty=y+next[k][1]; if(tx<0 || tx>4 || ty<0 || ty>4) continue; if(maze[tx][ty]==0&&vis[tx][ty]==0) { vis[tx][ty]=1; temp[step][0]=tx; //暂时存 temp[step][1]=ty; dfs(tx,ty,step+1); vis[tx][ty]=0; } } } int main() { int i,j; for(i=0;i<=4;i++) { for(j=0;j<=4;j++) { scanf("%d",&maze[i][j]); } } dfs(0,0,1);//从第一步开始，保存第一个点（0， 0） printf("%d\n",mi); for(i=0;i<mi;i++) { printf("(%d, %d)\n",ans[i][0],ans[i][1]); } return 0; }