洛谷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)
————————————————————————————————————————————————————————————————————————————分割线——————————————————————————————————————————————————————————————————————————————————————————————————————
正题开始 QWQ：
众所周知，要遍历迷宫所有（角落）就要用搜索。并且题目中要输出走的过程，那么我们可以用队列存一下它的x，y坐标和步数（也就是队尾，队头不用变），再用一下反悔操作（队列长度--），等下一次查找时将上一次的值覆盖掉就行了。
深搜模板·：
int find(int t) { if(满足输出条件) { 输出解; } else { for(int i=1;i<=尝试方法数;i++) if(满足进一步搜索条件) { 为进一步搜索所需要的状态打上标记; search(t+1); 恢复到打标记前的状态(反悔操作);//此题用来存队列 } } }
那么：
AC代码走起：
#include<cstdio> #include<iostream> #include<queue>//这个是队列用的（不用管疗 qwq） using namespace std; int m,n,bx,by,lx,ly,jz[17][17],dl[1001][2],check=0;//dl即为队列，jz是输入的那个01矩阵 int dx[4]={0,-1,0,1},k=0;//四种方向左上右下顺序排列（应题目要求） int dy[4]={-1,0,1,0};//d为delta。 void print()//打印操作 { for(int i=0;i<=k-1;i++)//k为队列长度，但是为什么到k-1呢？ 因为初始时k为0，往上4行能看到，我是从dl[0][0]和dl[0][1]开始存的 { printf("(%d,%d)",dl[i][0],dl[i][1]);//从队列第一项开始输出，一直到倒数第二项，因为倒数第一项没有入队呢QWQ if(i!=k-1)printf("->");//判断什么时候输出右移号。 else printf("->(%d,%d) ",lx,ly);//对最后一项进行特判 } return; } void move(int bx,int by) { int x=bx,y=by; if(x==lx&&y==ly)//判断是否到了最后一位 { print();check=1;return;//如果到最后走到指定位置了，执行输出操作，然后返回（反悔）。 } else for(int i=0;i<=3;i++)//左上右下 { if(x>0&&x<=m&&y>0&&y<=n&&jz[x+dx[i]][y+dy[i]]!=0) { jz[x][y]=0;//判断当前位置走过啦 dl[k][0]=x;dl[k][1]=y;k++;//入队操作QWQ move(x+dx[i],y+dy[i]);//就着这一步进行更深一层的走 jz[x][y]=1;k--;//反悔后退操作 } } } int main(){ scanf("%d%d",&m,&n); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) cin>>jz[i][j]; scanf("%d%d",&bx,&by); scanf("%d%d",&lx,&ly);//以上各种输入QWQ jz[bx][by]=0;//将当前起始位置设置为走过 move(bx,by);//执行走迷宫函数 if(check==0)printf("-1");//判断是否不符合条件。 return 0; }
完 结 撒 花 ✿ヽ(°▽°)ノ✿
对大家有帮助嘛？