题解 P1238 【走迷宫】

· · 题解

C++题解

基本思路：搜索 标记 打表 AC

代码呈上：

#include<iostream>//个人不建议使用万能头文件，容易报错；（本篇代码使用了，编译通不过）
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
int sum[50000][2];//用来记录每步的坐标；
int ax,ay,bx,by,k,pd;//ax，ay代表起点，bx，by代表终点，k是步数；
int cx[4]={0,-1,0,1};
int cy[4]={-1,0,1,0};//四个方向，左上右下；
bool temp[17][17];//标记：已经走过的路；
int map[17][17];//地图：1可走，0不可走；
void print()//输出函数；
{
    if(pd==0)//pd：判断是否有解，有解=1，无解=0；
    {
        pd=1; 
    }
    for(int h=0;h<=k-1;h++)
    cout<<"("<<sum[h][0]<<","<<sum[h][1]<<")"<<"->"; //输出中途步骤；
    cout<<"("<<bx<<","<<by<<")"<<endl;//输出终点；
}
void walk(int x,int y)//搜索回溯主体；
{
    if(x==bx&&y==by)//到达边界；
    {
        print();//输出解；
        return;
    }
    else
    {
        for(int i=0;i<=3;i++)
        if(map[x+cx[i]][y+cy[i]]==1&&temp[x+cx[i]][y+cy[i]]==0)//判断下一步是否可以走，一方面判断路是否可走，另一方面判断自己是否走过这条路；
        {
            temp[x][y]=1;//走过的路打上标记；
            sum[k][0]=x;
            sum[k][1]=y;//记录当前的坐标
            k++;//步数加1；
            walk(x+cx[i],y+cy[i]);
            temp[x][y]=0;
            k--;
            //回溯，这里的sum可以不用恢复；
        }
    }
}
int main()
{
    int m,n;//矩阵长宽；
    cin>>m>>n;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            cin>>map[i][j];//输入地图；

    cin>>ax>>ay;//起点；
    cin>>bx>>by;//终点；
    walk(ax,ay);//开始搜索；
    if(pd==0)//判断是否有解，如果没有解，输出-1；
    cout<<"-1";
    return 0;
}

经典的搜索题，输出增加了一个路径，当然只需要增加个二维数组也就OK了；

题还是有一些小陷阱：

1.做题之后忘记判断是否有解；

2.题目对搜索前进的方向有要求：左上右下，对于不需要输出路径的题，方向是没有要求的，（方向可能会影响效率，但是不会影响到最后的结果）但是对于有路径的题，方向可能会影响解的顺序；

3.k（步数）是否偏移；

（以上是贴主费了半天力没有做对的错误，大牛原谅我0.0）

这里再给大家一个基本的深搜模板：

int search(int t)
{
    if(满足输出条件)
    {
        输出解;
    }
    else
    {
        for(int i=1;i<=尝试方法数;i++)
            if(满足进一步搜索条件)
            {
                为进一步搜索所需要的状态打上标记;
                search(t+1);
                恢复到打标记前的状态;//也就是说的{回溯一步}
            }
    }
}

整个模板有几个地方需要注意：

1.第一个if是符合输出解的条件，第二个if是符合进一步搜索的条件；

2.下一步搜索时，不是使用return search(t+1)，直接search(t+1);（新手可能会注意不到这个关键的地方，以至于每次写完不知道为什么只得到一个答案就返回主程序了）

3.for循环之后的if可以是多个;

4.for循环边界，例如：

1>方向是四个，那么边界肯定就是4；（帖主用3，是因为从0开始的）

2>素数环需要尝试1至20，那么边界就是20；

如果想要了解更多的知识，请关注我的博客（觉得鄙人题解写的可以的也可以进来点个赞呐，亲）：https://www.luogu.org/blog/AHacker/

(近期贴主还会在博客更新搜索的详细解释)