洛谷1238 走迷宫
题目描述
有一个m*n格的迷宫(表示有m行、n列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这m*n个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息(用-l表示无路)。
输入输出格式
输入格式：
第一行是两个数m，n(1<m，n<15)，接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点。
输出格式：
所有可行的路径，描述一个点时用(x，y)的形式，除开始点外，其他的都要用“一>”表示方向。
如果没有一条可行的路则输出-1。
输入输出样例
输入样例#1：
5 6
1 0 0 1 0 1
1 1 1 1 1 1
0 0 1 1 1 0
1 1 1 1 1 0
1 1 1 0 1 1
1 1
5 6
输出样例#1：
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(
【思路】
回溯法。
因为题目要求输出不同路径，所以我们采用回溯法搜索路径并输出。
需要注意的有：
1、 起始点==终点则输出-1
2、 一定不要忘记标记起始点。
【代码】
1 #include<iostream> 2 #include<cstring> 3 #include<queue> 4 #include<vector> 5 using namespace std; 6 7 const int maxn = 30; 8 const int dx[]={0,-1,0,1}; 9 const int dy[]={-1,0,1,0}; 10 11 int G[maxn][maxn]; 12 int vis[maxn][maxn]; 13 int A[maxn*maxn][3]; 14 int n,m,e_x,e_y; 15 bool f=false; 16 17 inline bool inside(int x,int y) { 18 return x>=1 && x<=n && y>=1 && y<=m && G[x][y]; 19 } 20 21 void dfs(int x,int y,int d) 22 { 23 if(x==e_x && y==e_y) 24 { 25 for(int i=0;i<d-1;i++) 26 cout<<"("<<A[i][0]<<","<<A[i][1]<<")->"; 27 cout<<"("<<e_x<<","<<e_y<<")"<<endl; 28 f=true; 29 return ; 30 } 31 for(int i=0;i<4;i++) 32 { 33 int xx=x+dx[i],yy=y+dy[i]; 34 if(inside(xx,yy) && !vis[xx][yy]) 35 { 36 vis[xx][yy]=1; 37 A[d][0]=xx; A[d][1]=yy; 38 dfs(xx,yy,d+1); 39 vis[xx][yy]=0; 40 } 41 } 42 } 43 44 int main() { 45 ios::sync_with_stdio(false); 46 cin>>n>>m; 47 for(int i=1;i<=n;i++) 48 for(int j=1;j<=m;j++) 49 cin>>G[i][j]; 50 int f_x,f_y; 51 cin>>f_x>>f_y>>e_x>>e_y; 52 if(f_x==e_x && f_y==e_y) { 53 cout<<-1; 54 return 0; 55 } 56 57 A[0][0]=f_x, A[0][1]=f_y; 58 vis[f_x][f_y]=1; 59 dfs(f_x,f_y,1); 60 61 if(!f) cout<<-1; 62 return 0; 63 }