题解 P2802 【回家】

· · 题解

一道DFS，但是要处理的东西挺多的。

先说一下思路吧。

首先它的读入就是不同的数字，所以如果读进来的是小H的出发地或家，要进行记录，这要方便一点。

在DFS中，需要改变的元素有四个，两个是横纵坐标，还有时间和血量。

如果时间比最小值小，且到达终点，进行最小值的改变。

定义方向增量，要注意回溯（一定要变成原来坐标的数字，若直接变为1，只能得80分）

贴上AC代码：

#include <iostream>
#include <cstdio>
using namespace std;
int n,m;//矩阵大小
int a[10][10];//矩阵存储
int x1,y1,x2,y2;//起点坐标和终点坐标
int ans=1000000000;//最小值，定义最大的
int xy[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//方向增量，四个方向
void input ()//读入函数
{
    cin>>n>>m;//读入矩阵大小
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            cin>>a[i][j];//读入数字
            if (a[i][j]==2) {
                x1=i;
                y1=j;//如果为起点，记录坐标
            }
            if (a[i][j]==3) {
                x2=i;
                y2=j;//如果为终点，也记录坐标
            }
        }
    }
    return;//结束读入
}
void dfs (int x,int y,int time,int hp){//DFS核心函数
    if (time>=ans || hp<=0) return;//如果没到边界时间就超过最小值，或者没血了，直接回溯
    if (x==x2 && y==y2) {//若到达终点
        if (time<ans) ans=time;//比时间小，存储
        return;
    }
    int t=a[x][y];//记录原来的值
    if (a[x][y]==4) hp=6;//如果捡到鼠标，血量变为6
    for (int i=0;i<4;i++){
        int xx=x+xy[i][0];//横坐标增加
        int yy=y+xy[i][1];//纵坐标增加
        if (xx>=0 && yy>=0 && xx<=n && yy<=m && a[xx][yy]!=0) {//如果没框到边界，且不为障碍物，DFS
            a[x][y]=0;//记为障碍物
            dfs (xx,yy,time+1,hp-1);//DFS新坐标
            a[x][y]=t;//回溯（一定要为原始数字）
        }
    }
    return;
}
int main ()
{
    input ();
    dfs (x1,y1,0,6)
    if (ans==1000000000) cout<<-1<<endl;//如果没变，无解
    else cout<<ans<<endl;//否则输出
    return 0;
}
祝大家天天AC！！！