描述
定义一个二维数组：
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)
思路
这种问题搜索不难，难的是要怎么去存储路径。一开始想用BFS搜索最短路的，但是没有想好怎么存储路径，后来改用DFS写，就好多了。记得要回溯。
代码
#include<bits/stdc++.h>
using namespace std;int a[6][6];
int vis[6][6];
int n=5;
vector<string> v;
vector<string> ans;string gets(int x,int y){char ch[6];char xx=x+'0';char yy=y+'0';ch[0]='(';ch[1]=xx;ch[2]=',';ch[3]=' ';ch[4]=yy;ch[5]=')';return ch;
}void dfs(int x,int y){if(x==4&&y==4){if(ans.empty()) ans=v;if(ans.size()>v.size()) ans=v;return;}if(x+1<n&&!vis[x+1][y]&&a[x+1][y]==0){vis[x+1][y]=1;v.push_back(gets(x+1,y));dfs(x+1,y);v.pop_back();vis[x+1][y]=0;}if(y+1<n&&!vis[x][y+1]&&a[x][y+1]==0){vis[x][y+1]=1;v.push_back(gets(x,y+1));dfs(x,y+1);v.pop_back();vis[x][y+1]=0;}
}int main(){for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>a[i][j];}}vis[0][0]=1;v.push_back("(0, 0)");dfs(0,0);for(int i=0;i<ans.size();i++) cout << ans[i] <<endl;return 0;
}