题解 P2802 【回家】

· · 题解

//卡了很久的题，希望看到的，不要抄袭，最好看懂注释自己尝试写出来，这样才有意义

//首先要注意，判断点的数值（也就是4,3，死掉）要放在判断搜索条件外面

//其次要注意的回溯的时候不能只进行自加自减操作，要把它取出来，不然会wa一个点

//还有就是，要设置访问过的数组（我也不知道什么用，习惯加上）

#include<bits/stdc++.h>//偷懒专用 
using namespace std;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}//这是快读，想看的可以参考，不想看的可以换成cin或者scanf 
int pop=6,ans,n,mi=10000,m,a[10][10];//pop为血条 ，ans为步数，n，m为边界，mi为答案，a数组存储数值 
int f[5][3]={{0,0,0},{0,0,1},{0,0,-1},{0,1,0},{0,-1,0}};//至于为什么这么做，是用来遍历，少写代码，不然要写四个if，爆搜，有点小麻烦 
int b[10][10];//是否访问过 
void dfs(int x,int y)//以下为搜索过程 
{   
    if(pop==0)
        return;//如果死了，就返回上一步 
    if(a[x][y]==4)
        pop=6;//如果是鼠标，就加满血 
    if(a[x][y]==3)
    {
        if(ans<mi)
            mi=ans;
        return;
    }//如果到了，记录答案，存储最小的 
    for(int i=1;i<=4;++i)
     {
        int nx=x+f[i][1];//改变x的位置 
        int ny=y+f[i][2];//改变y的位置 
        if(nx>0&&ny>0&&nx<=n&&ny<=m&&a[nx][ny]!=0&&b[nx][ny]==0)
         {
            int p=pop;//为了回溯 ，不然会wa一个点，如果用自加和自减 
            pop--;//血条减一 
            ans++;//步数加一 
            b[nx][ny]=1;//设置为访问过 
            dfs(nx,ny);//搜索 
            b[nx][ny]=0;//回溯 
            ans--;//回溯 
            pop=p;//回溯 
         }
     }
}
int main()
{
    int aa,bb; 
    n=read();
    m=read();//用快读读入的，可以啊改，无所谓 
    for(int i=1;i<=n;++i)
     for(int j=1;j<=m;++j)
     {
      a[i][j]=read();//读入数值 
      if(a[i][j]==2)
       {
        aa=i;
        bb=j;
       }//记录起点位置 
      }
    dfs(aa,bb);
    if(mi==10000)
    {
        cout<<-1;
        return 0;
    }//如果没到达过 
    cout<<mi;//到达过 
    return 0;//完美落幕 
}

//希望通过