Luogu P2802 回家

题目描述

小H在一个划分成了n*m个方格的长方形封锁线上。每次他能向上下左右四个方向移动一格（当然小H不可以静止不动），但不能离开封锁线，否则就被打死了。刚开始时他有满血6点，每移动一格他要消耗1点血量。一旦小H的血量降到 0，他将死去。他可以沿路通过拾取鼠标（什么鬼。。。）来补满血量。只要他走到有鼠标的格子，他不需要任何时间即可拾取。格子上的鼠标可以瞬间补满，所以每次经过这个格子都有鼠标。就算到了某个有鼠标的格子才死去，他也不能通过拾取鼠标补满 HP。即使在家门口死去，他也不能算完成任务回到家中。

地图上有 5 种格子：

数字 0：障碍物。

数字 1：空地，小H可以自由行走。

数字 2：小H出发点，也是一片空地。

数字 3：小H的家。

数字 4：有鼠标在上面的空地。

小H能否安全回家？如果能，最短需要多长时间呢？

输入输出格式

输入格式：

第一行两个整数n,m，表示地图的大小为n*m。

下面 n 行，每行 m 个数字来描述地图。

输出格式：

一行，若小H不能回家，输出-1,否则输出他回家所需最短时间。

输入输出样例

输入样例#1：

输出样例#1：

说明

1<=n,m<=9

 1 //一道挺水的题。
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<cstdlib>
 7 using namespace std;
 8 int n,m,map[10][10],nx,ny,ans=200;
 9 bool a[10][10];
10 void dfs(int x,int y,int b,int s){//坐标，血，次数 
11     b--;
12     if(x==0||y==0||x>n||y>m||map[x][y]==0||a[x][y]||b==0||s>ans)//出界，障碍，搜过，死亡，大于答案都要结束 
13         return;
14     if(map[x][y]==3){//记录答案 
15         ans=min(ans,s);
16         return;
17     }
18     if(map[x][y]==4)//鼠标 
19         b=6;
20     s++;
21     a[x][y]=1;
22     dfs(x+1,y,b,s);//}
23     dfs(x,y+1,b,s);//|}
24     dfs(x-1,y,b,s);//|}向四周搜 
25     dfs(x,y-1,b,s);//}
26     a[x][y]=0;
27 }
28 int main(){
29     int i,j;
30     cin>>n>>m;
31     for(i=1;i<=n;i++)
32         for(j=1;j<=m;j++){ 
33             cin>>map[i][j];
34             if(map[i][j]==2){//记录起点 
35                 nx=i;
36                 ny=j;
37             }
38     }
39     dfs(nx,ny,6,0);//开搜，从起点， 
40     if(ans==200)//一开始设的是200，如果没变，说明没结果，则输出-1(有点危险，再大点更好，int最大2147483647) 
41         cout<<-1;
42     else
43         cout<<ans;
44     return 0;
45 }