洛谷—— P1238 走迷宫

时间：2023-03-09 13:27:19
洛谷—— P1238 走迷宫

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，搜索顺序只能是 左 上 右 下
 #include <cstdio>

 int n,m,sx,sy,tx,ty;

 bool vis[][],flag;

 bool can_go[][];

 int fx[]={,-,,};

 int fy[]={-,,,};

 struct Type {

     int x[],y[];

     int cnt;

 }ans;

 void DFS(int nowx,int nowy)

 {

     if(nowx==tx&&nowy==ty)

     {

         flag=;

         printf("(%d,%d)->",sx,sy);

         for(int i=; i<ans.cnt; ++i)

             printf("(%d,%d)->",ans.x[i],ans.y[i]);

         printf("(%d,%d)\n",ans.x[ans.cnt],ans.y[ans.cnt]);

         return ;

     }

     for(int i=; i<; ++i)

     {

         int tox=nowx+fx[i],toy=nowy+fy[i];

         if(tox<||toy<||tox>m||toy>n) continue;

         if(vis[tox][toy]||!can_go[tox][toy]) continue;

         vis[tox][toy]=;

         ans.x[++ans.cnt]=tox;

         ans.y[ans.cnt]=toy;

         DFS(tox,toy);

         vis[tox][toy]=;

         ans.cnt--;

     }

 }

 inline void read(int &x)

 {

     x=; register char ch=getchar();

     for(; ch>''||ch<''; ) ch=getchar();

     for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';

 }

 int Aptal()

 {

     read(m),read(n);

     for(int x,i=; i<=m; ++i)

       for(int j=; j<=n; ++j)

         read(x),can_go[i][j]=x;

     read(sx),read(sy),read(tx),read(ty);

     vis[sx][sy]=; DFS(sx,sy);

     if(!flag) puts("-1");

     return ;

 }

 int Hope=Aptal();

 int main(){;}

相关文章