迷宫问题
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- 定义一个二维数组：
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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
- 输入
- 一个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
- 样例输出
-
(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | #include<iostream> #include<cstdio> #include<cstring> using namespace std; int map[7][7]; struct S{ int x; int y; }step[26]; bool visited[7][7]; int x_arr[5]={0,1,-1,0,0}; int y_arr[5]={0,0,0,1,-1}; int DFS(int x,int y,int step_i,int max){ if(x<1||x>5||y<1||y>5||map[x][y]==1||visited[x][y])return 30; if(x==5&&y==5){ step[step_i].x=x; step[step_i].y=y; return step_i; } visited[x][y]=true; int min=30; for(int i=1;i<=4;i++){ int t=DFS(x+x_arr[i],y+y_arr[i],step_i+1,min); if(t<min)min=t; } visited[x][y]=false; if(min<30){//从递归的思路上去看，只管当前节点：如果min<30，当前节点就一定是当前路径上的一点，那么要把它加入到当前记录的路径中；如果有比他长的路径，那么短的路径会覆盖长的路径（此处还有问题？？但是如果长的路径在短的路径后面，路径记录就会不准确，应该需要max参数，这道题应该是数据弱吧，） step[step_i].x=x; step[step_i].y=y; return min; } return 30; } int main(){ memset(map,1,sizeof(map)); memset(visited,false,sizeof(visited)); for(int i=1;i<=5;i++){ for(int j=1;j<=5;j++){ scanf("%d",&map[i][j]); } } int last=DFS(1,1,1,30); for(int i=1;i<=last;i++){ printf("(%d, %d)\n",step[i].x-1,step[i].y-1); } } |