P1238 走迷宫
题目描述
有一个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)
1 /* 2 dfs+回溯 3 由于没有spj 4 那就 按照左 下 右 上的方向来搜 5 要不WA成狗你也改不出来 6 */ 7 #include <queue> 8 #include <cstdio> 9 #include <cctype> 10 11 const int MAXN=50; 12 const int MAXM=150; 13 14 int n,m,Sx,Sy,Tx,Ty,cnt; 15 16 int map[MAXN][MAXN],X[MAXN],Y[MAXN]; 17 18 int x[4]={0,-1,0,1}; 19 int y[4]={-1,0,1,0}; 20 21 bool vis[MAXN][MAXN]; 22 23 bool flag; 24 25 inline void read(int&x) { 26 int f=1;register char c=getchar(); 27 for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar()); 28 for(;isdigit(c);x=x*10+c-48,c=getchar()); 29 x=x*f; 30 } 31 32 void dfs(int xx,int yy) { 33 if(xx==Tx&&yy==Ty) { 34 flag=true; 35 printf("(%d,%d)->",Sx,Sy); 36 for(int i=1;i<cnt;++i) 37 printf("(%d,%d)->",X[i],Y[i]); 38 printf("(%d,%d) ",Tx,Ty); 39 return; 40 } 41 for(int i=0;i<4;++i) { 42 int nx=xx+x[i]; 43 int ny=yy+y[i]; 44 if(!vis[nx][ny]&&map[nx][ny]&&nx>0&&ny>0&&nx<=n&&ny<=m) { 45 X[++cnt]=nx; 46 Y[cnt]=ny; 47 vis[nx][ny]=true; 48 dfs(nx,ny); 49 vis[nx][ny]=false; 50 --cnt; 51 } 52 } 53 return; 54 } 55 56 int hh() { 57 // freopen("1.out","w",stdout); 58 read(n);read(m); 59 for(int i=1;i<=n;++i) 60 for(int j=1;j<=m;++j) 61 read(map[i][j]); 62 read(Sx);read(Sy);read(Tx);read(Ty); 63 flag=false; 64 vis[Sx][Sy]=true; 65 dfs(Sx,Sy); 66 if(!flag) printf("-1 "); 67 return 0; 68 } 69 70 int sb=hh(); 71 int main(int argc,char**argv) {;}