问题描述 定义一个二维数组： 定义一个5*5的数组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） 题意思路： 可以深搜也可以广搜，因为没写过深搜的博客，就用深搜写的。 代码：
#include <iostream> using namespace std; int maze[5][5]; struct point //定义点结构体 { int x,y; }; int mini_k = 100000; //最小的k point path[1000]; //暂存路径的数组 point shortest_path[1000]; //最短路径的数组 int flag[5][5]={0}; //标记是否访问过,初始化为全0 bool inside(int x,int y)//判断x,y是否在地图内 { if(x>=0&&x<5&&y>=0&&y<5)return true; return false; } void dfs(int x,int y,int k)//对点 (x,y) 进行dfs遍历 当前是第k步 { if(x==4&&y==4) //cout<<"到终点了"<<endl; { if(k<mini_k)//更新最短路径数组 { mini_k = k; for(int i=0;i<k;i++) { shortest_path[i] = path[i]; } } return; } if(inside(x+1,y) && flag[x+1][y]==0 && maze[x+1][y] ==0)//走四个方向 { flag[x+1][y] = 1; path[k].x = x+1; path[k].y = y; dfs(x+1 ,y ,k+1); flag[x+1][y] = 0; } if(inside(x,y+1) && flag[x][y+1]==0 && maze[x][y+1] ==0) { flag[x][y+1] = 1; path[k].x = x; path[k].y = y+1; dfs(x ,y+1 ,k+1); flag[x][y+1] = 0; } if(inside(x-1,y) && flag[x-1][y]==0 && maze[x-1][y] ==0) { flag[x-1][y] = 1; path[k].x = x-1; path[k].y = y; dfs(x-1 ,y ,k+1); flag[x-1][y] = 0; } if(inside(x,y-1) && flag[x][y-1]==0 && maze[x][y-1] ==0) { flag[x][y-1] = 1; path[k].x = x; path[k].y = y-1; dfs(x ,y-1 ,k+1); flag[x][y-1] = 0; } } int main() { int i,j; for(i=0;i<5;i++) { for(j=0;j<5;j++) { cin>>maze[i][j]; } } flag[0][0]=1; path[0]={0,0}; dfs(0,0,1); for(int i=0;i<mini_k;i++) { cout<<'('<<shortest_path[i].x<<','<<" "<<shortest_path[i].y<<')'<<endl; } return 0; }感悟：这道题在深度搜索的基础上，加了保存了最短路径的代码。
