P2802 回家

· · 题解

原题链接

不知道自己怎么错的看过来，这有六种错法

难度：普及-（但是要小心，多坑）

较为普通的 DFS ，输入时记录初始点，将开始的 mouse（鼠标）数量设为 6，直接开始递归。但要注意以下几点：

  1. “ 一旦小H的 血量降到 0， 他将死去 ”，也就是说当小 H 血量为 1，且本格不能补充，就已经可以视为死亡了。我的做法是在每次递归开始时判断，如果鼠标数量为 0 就直接返回。

  2. “ 他可以沿路通过拾取鼠标（什么鬼。。。）来补满血量 ” 即每次遇到可以拾取鼠标的点后鼠标数量回到 6。

  3. 本题是求最小值的 DFS 算法，所以并没有明确的结束标记，我的做法是将 m*n 即所有点的数量设为上线。

记我的失败之路（无特殊说明错误均为 wrong answer）：

  1. 在移动后进行边界判断时，将 m 和 n 搞反

    • 得分 40 可以通过测试点 1 、3 、4 、7（5 、8 TLE ）。失败样例一

  2. 在遇到可以拾取鼠标的点后，先将血量回复到 6 。

    • 得分 90 第 10 个点错误。失败样例二

  3. 将步数上界设置得过小，比如 m*n/2 。

    • 得分 50 可以通过测试点 1 、2 、3 、7 、10 。失败样例三

  4. 没有设置步数上界

    • 得分 40 可以通过测试点 1 、2 、4、 7 （ 其余 MLE 错误 ）。失败样例四

  5. 在超出步数上界后将回答设为 -1 。

    • 得分 60 未通过测试点 5 、6 、8 、9。失败样例五

  6. ans 初值过小或者捡到鼠标后只血量只加一亦或者捡到鼠标后血量恢复到5。

    • 得分80 未通过测试点 6 、9。失败样例六

代码实现：

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
void dfs(int x,int y,int mou);
long long a[11][11],dir[4][2]={1,0,-1,0,0,1,0,-1};
//此处的 dir 数组用于计算 小H 的移动
int tx,ty,lx,ly,n,m,mou=6,times=0,minans=1<<30;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]==2){
                tx=i;ty=j; 
                //记录开始点
            }
            if(a[i][j]==3){
                lx=i;ly=j;
                //记录结束点
            }
        }
    dfs(tx,ty,mou);
    //开始搜索
    if(minans!=1<<30) cout<<minans<<endl;
    else cout<<-1<<endl;
    //如果此时 minans 与初值相等，则没有找到可行路径 QAQ
    return 0;
} 
void dfs(int x,int y,int mou){
    if(mou==0||times>m*n||times>minans) return;
    //如果血量为0或者超出步数上界或者此时的步数已经超过了答案
    if(a[x][y]==4) mou=6;
    if(x==lx&&y==ly) minans=min(times,minans);
    else{
        for(int i=0;i<4;i++){
            tx=x+dir[i][0];
            ty=y+dir[i][1];
            if(tx<=0||tx>n||ty<=0||ty>m||a[tx][ty]==0) continue;
            //边界判断和是否撞墙
            ++times;
            dfs(tx,ty,mou-1);
            --times;
        }
    }
}

测试详情

看在我这么多次出错，又把它们都好好总结的份上，不通过，不点赞你对的起你的良心吗……（写完题解的作者已泪崩）你们看我这么可耐，就别欺负我了

记这万红之中的一抹亮色