题解 P2802 【回家】

肖泽源 · 2019-08-23 15:42:21 · 题解

dfs+剪枝

具体思路可借其他深搜大佬的题解。

代码如下

#include<bits/stdc++.h>
using namespace std;
int n,m;int minn=1e9;//记录最快到家的时间
int a[15][15];//地图
int p,t;//记录家的坐标
bool b[15][15],flag;//b标记有没有走过，
int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//上下左右移动
void dfs(int x,int y,int hp,int time)
{
    if(bve==0)return ;
    //if(flag==1)return ;//第一次错在这里，并非第一次找到的答案为最优解

    if(x==p&&y==t&&hp>0)
    {
        flag=1;
        minn=min(minn,time);//找到最快的解，并存在minn中
        return ;
    }//也可以if（time>minn）return;剪枝
    for(int i=0;i<4;i++)//深搜
    {
        int tx,ty;//移动
        tx=x+d[i][0];
        ty=y+d[i][1];
        if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&b[tx][ty]==0&&a[tx][ty]!=0)
        {
            //分三种情况讨论
            if(a[tx][ty]==1)
            {
                b[tx][ty]=1;
                dfs(tx,ty,hp-1,time+1);
                b[tx][ty]=0;
            }
            if(a[tx][ty]==3)
            {
                b[tx][ty]=1;
                dfs(tx,ty,hp-1,time+1);
                b[tx][ty]=0;
            }
            if(a[tx][ty]==4)
            {
                if(hp==1)return ;//如果血量已经是1了，就算下个是有鼠标的格子， 他也不能通过拾取鼠标补满 HP
                b[tx][ty]=1;
                dfs(tx,ty,6,time+1);
                b[tx][ty]=0;
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            if(a[i][j]==2)//找到出发点，并记录坐标
            {
                x=i;
                y=j;
            }
            else if(a[i][j]==3)//找到家，并记录坐标
            {
                p=i;
                t=j;
            }
        }
    b[x][y]=1;//标记出发点已走过
    dfs(x,y,6,0);//x,y为当前坐标（即为出发点），6为当前hp，0记录时间
    if(flag==0)printf("-1");//如果没有标记，则没有到家，输出-1
    else printf("%d",minn);//否则输出最快到家的时间
    return 0;
}