题解 P2802 【回家】

· · 题解

其实洛谷对一道题的难度评判一定程度决定了该用什么算法，

当然，这题不仅是难度评判，还有数据范围，

难度是普及-，n，m<=9，很明显，大家可以放心dfs，我稍微减了一下枝，结果用时是0ms，dfs可行。

既然是dfs，那就很简单了，题目只是走迷宫稍稍多了一点元素HP，导致了一下两个结果：

1、多了返回的条件； 2、有走不到家的情况。

那解决很简单，若没HP就返回，若一圈dfs下来min还是初值，那么就可以输出-1了。

当然，细节方面，首先输入时就记录下起点坐标。

其次搜索前用t把当前位置原本的元素记下来，然后给它先标为障碍，以免死循环来回，搜完四面再变回原来的元素

于是dfs代码（有点长，处理起来挺麻烦的）：

#include<stdio.h>
int a[11][11],min=10000000;
int n,m;
void dfs(int x,int y,int ans,int hp)
{
    int t;
    if(ans>=min||hp<=0) return;//如果走的步数已经大于当时的最短步数了或没HP了，返回
    if(a[x][y]==3)//如果到家
    {
        if(ans<min) min=ans;//如果比之前走的步数要少，记录下来
        return;//继续去找
    }
    if(a[x][y]==4) hp=6;//如果地上有鼠标（呵呵……），补满血（真厉害……）
    switch (a[x][y])//记录下当前元素
    {
        case 1:t=1; break;
        case 2:t=2; break;
        case 4:t=4; break;
    }
       a[x][y]=0;//标记为障碍物，以免重复搜索
        if(a[x+1][y]!=0&&x+1<=n) dfs(x+1,y,ans+1,hp-1);//往下
        if(a[x-1][y]!=0&&x-1>0) dfs(x-1,y,ans+1,hp-1);//上
        if(a[x][y+1]!=0&&y+1<=m) dfs(x,y+1,ans+1,hp-1);//右
        if(a[x][y-1]!=0&&y-1>0) dfs(x,y-1,ans+1,hp-1);//左，记住，别忘越界判断（其实没有也行，全局变量初值都是0，就是障碍物）
       a[x][y]=t;//搜完，变回原来元素
}
int main()
{
    int i,j,x,y;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
     {
         for(j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            if(a[i][j]==2){x=i; y=j;}//如果是起点，记录坐标
        }
    }
    dfs(x,y,0,6);//一顿爆搜
  if(min==10000000) printf("-1"); else printf("%d",min);//如果min还是初值，输出-1，否则，输出最少步数
  return 0;
}