啥是迷宫问题？
迷宫问题，简单来说就是在给定区域内，找到一条甚至所有从某个位置到另一个位置的移动路线。
如果细来讲，我们可以把迷宫化为一个平面矩阵，通过行、列来确定位置，对应位置不同的内容表示不同的地图信息。
在c++里，我们一般用二维数组来存储，例如n*n大小的地图就是m[n][n]，地图中存在空地或障碍物，就可以使用 0表示空地，1表示障碍物。
好啦，咱们弄懂了迷宫问题，那啥是DFS呢？
DFS,又叫深度优先搜索（Depth First Sreach），说白了，就是往深里扎，用bool型数组标记走过的路，通过判断前后左右有没有障碍物或走过的路来走下一步，
其实就是电脑爬墙走。例如：现在在[x,y]点，我要判断[x+1,y],[x-1,y],[x,y+1],[x,y-1]点，是不是有障碍物或走过的路一样。可以用递归来做。可判断方向的方法需要引入一个技术：偏移量
先定义俩个数组：
dx[4]={-1,1,0,0}; dy[4]={0,0,-1,1);
然后
//当前坐标 x,y for(int i=0;i<4;i++){ int nx=x+dx[i],ny=y+dy[i]; //...; }
在看到nx和ny,就会发现：这不就是[x+1,y],[x-1,y],[x,y+1],[x,y-1]的坐标吗？所以，这就成了dfs里最重要的一步：判断前后左右
==============================================================
总之，其实整个路径的判断的描述过程就是如上图一样的树。
===============================================================
so，上代码
1 //0:空地 1:障碍物 2 #include<iostream> 3 #include<vector> 4 using namespace std; 5 vector<int> px,py; 6 int dx[4]={-1,1,0,0}; 7 int dy[4]={0,0,-1,1}; 8 int vis[20][20],ans=0,r,c,sx,sy,fx,fy; 9 char g[20][20]; 10 void dfs(int x,int y) 11 { 12 if(x==fx && y==fy)//输出路径 13 { 14 ans++; 15 printf("%d号路径：(%d,%d)",ans,sx,sy); 16 for(int i=1;i<px.size();i++) 17 { 18 printf("->(%d,%d)",px[i],py[i]); 19 } 20 cout << endl; 21 return ; 22 } 23 for(int i=0;i<4;i++) 24 { 25 int nx=x+dx[i],ny=y+dy[i];//偏移量 26 if(nx<1 || nx>r || ny<1 || ny>c) continue;//是否越界 27 if(vis[nx][ny]==0 && g[nx][ny]=='0')//回溯 28 { 29 vis[nx][ny]=1; 30 px.push_back(nx),py.push_back(ny); 31 32 dfs(nx,ny); 33 34 vis[nx][ny]=0; 35 px.pop_back(),py.pop_back(); 36 } 37 } 38 } 39 int main() 40 { 41 cin >> r>> c; 42 for(int i=1;i<=r;i++){ 43 for(int j=1;j<=c;j++){ 44 cin >> g[i][j]; 45 } 46 } 47 cin >> sx>>sy >> fx>> fy; 48 vis[sx][sy]=1;//起点标记 49 px.push_back(sx),py.push_back(sy);//vector存起点 50 dfs(sx,sy); 51 52 if(ans==0) 53 { 54 cout << "没有路径"<<endl; 55 } 56 return 0; 57 }