https://www.luogu.org/problem/show?pid=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)->(5,6)
没有SJ，搜索顺序只能是 左 上 右 下
1 #include <cstdio> 2 3 int n,m,sx,sy,tx,ty; 4 bool vis[15][15],flag; 5 bool can_go[15][15]; 6 int fx[4]={0,-1,0,1}; 7 int fy[4]={-1,0,1,0}; 8 9 struct Type { 10 int x[2250],y[2250]; 11 int cnt; 12 }ans; 13 14 void DFS(int nowx,int nowy) 15 { 16 if(nowx==tx&&nowy==ty) 17 { 18 flag=1; 19 printf("(%d,%d)->",sx,sy); 20 for(int i=1; i<ans.cnt; ++i) 21 printf("(%d,%d)->",ans.x[i],ans.y[i]); 22 printf("(%d,%d)\n",ans.x[ans.cnt],ans.y[ans.cnt]); 23 return ; 24 } 25 for(int i=0; i<4; ++i) 26 { 27 int tox=nowx+fx[i],toy=nowy+fy[i]; 28 if(tox<1||toy<1||tox>m||toy>n) continue; 29 if(vis[tox][toy]||!can_go[tox][toy]) continue; 30 vis[tox][toy]=1; 31 ans.x[++ans.cnt]=tox; 32 ans.y[ans.cnt]=toy; 33 DFS(tox,toy); 34 vis[tox][toy]=0; 35 ans.cnt--; 36 } 37 } 38 39 inline void read(int &x) 40 { 41 x=0; register char ch=getchar(); 42 for(; ch>'9'||ch<'0'; ) ch=getchar(); 43 for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0'; 44 } 45 46 int Aptal() 47 { 48 read(m),read(n); 49 for(int x,i=1; i<=m; ++i) 50 for(int j=1; j<=n; ++j) 51 read(x),can_go[i][j]=x; 52 read(sx),read(sy),read(tx),read(ty); 53 vis[sx][sy]=1; DFS(sx,sy); 54 if(!flag) puts("-1"); 55 return 0; 56 } 57 58 int Hope=Aptal(); 59 int main(){;}
