Problem Description
有一个m*n格的迷宫（表示有m行、n列），其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，输入这m*n个数据和起始点、结束点（起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号）。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息（用-1表示无路）。
Input
第一行是两个数m，n（1< m, n< 15)，接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点。
Output
所有可行的路径，输出时按照左上右下的顺序。描述一个点时用（x，y）的形式，除开始点外，其他的都要用“->”表示。如果没有一条可行的路则输出-1。
Example Input
5 4 1 1 0 0 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 5 4Example Output
(1,1)->(1,2)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4) (1,1)->(1,2)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4) (1,1)->(1,2)->(2,2)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4) (1,1)->(1,2)->(2,2)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4) (1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4) (1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4) (1,1)->(2,1)->(2,2)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4) (1,1)->(2,1)->(2,2)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)
解题思路：
用二维数组或者结构体存储坐标信息，每一次递归都会保存新的坐标信息。到了终点就输出呗~。一道简单的DFS题。但要注意走的方向先后顺序！！！
AC代码如下：
#include<iostream> #include<cstring> #define maxn 30 using namespace std; int ex,ey; int m,n; int maze[maxn][maxn]; int vis[maxn][maxn]; int A[maxn*maxn*maxn*maxn][3]; int mov[4][2]={0,-1,-1,0,0,1,1,0};//坑爹的题要求只能左上右下的顺序走╭(′▽`)╯ bool flag=false; bool inside(int a,int b) { if(a>=1&&a<=m&&b>=1&&b<=n) return true; return false; } void ways(int sx,int sy,int d) { if(sx==ex&&sy==ey) { for(int i=0;i<d-1;i++) cout<<"("<<A[i][0]<<","<<A[i][1]<<")->"; cout<<"("<<A[d-1][0]<<","<<A[d-1][1]<<")"<<endl; flag=true; return ; } for(int i=0;i<4;i++) { int xx=sx+mov[i][0]; int yy=sy+mov[i][1]; if(!vis[xx][yy]&&inside(xx,yy)&&maze[xx][yy]) { A[d][0]=xx; A[d][1]=yy; vis[xx][yy]=1; ways(xx,yy,d+1); vis[xx][yy]=0; } } } int main(void) { int sx,sy; memset(vis,0,sizeof(vis)); cin>>m>>n; for(int i=1;i<=m;i++) for(int j=1;j<=n ;j++) cin>>maze[i][j]; cin>>sx>>sy>>ex>>ey; vis[sx][sy]=1; A[0][0]=sx; A[0][1]=sy; flag=false; ways(sx,sy,1); if(!flag) cout<<"-1"<<endl; } /*************************************************** User name: Achan Result: Accepted Take time: 0ms Take Memory: 236KB Submit time: 2017-08-05 11:23:59 ****************************************************/
