P2802 回家 解题报告
1. problem
点击查看题目
回家
题目描述
小 H 在一个划分成了 \(n \times m\) 个方格的长方形封锁线上。 每次他能向上下左右四个方向移动一格（当然小 H 不可以静止不动）， 但不能离开封锁线，否则就被打死了。 刚开始时他有满血 \(6\) 点，每移动一格他要消耗 \(1\) 点血量。一旦小 H 的血量降到 \(0\)， 他将死去。 他可以沿路通过拾取鼠标（什么鬼。。。）来补满血量。只要他走到有鼠标的格子，他不需要任何时间即可拾取。格子上的鼠标可以瞬间补满，所以每次经过这个格子都有鼠标。就算到了某个有鼠标的格子才死去， 他也不能通过拾取鼠标补满 HP。 即使在家门口死去， 他也不能算完成任务回到家中。
地图上有五种格子：
0：障碍物。
1：空地， 小 H 可以自由行走。
2：小 H 出发点， 也是一片空地。
3：小 H 的家。
4：有鼠标在上面的空地。
小 H 能否安全回家？如果能， 最短需要多长时间呢？
输入格式
第一行两个整数 \(n,m\)， 表示地图的大小为 \(n \times m\)。
下面 \(n\) 行， 每行 \(m\) 个数字来描述地图。
输出格式
一行， 若小 H 不能回家， 输出 -1，否则输出他回家所需最短时间。
样例 #1
样例输入 #1
3 3
2 1 1
1 1 0
1 1 3
样例输出 #1
4
提示
对于所有数据，\(1 \le n,m \le 9\)。
2. 思路
1. 题意
判断小H是否能够回家.
- 如果不能,输出
-1. - 如果能,输出最短路径.
2. 算法
使用\(DFS\)算法,从起点开始,如果能走,就把这个点记录,然后继续搜索.
3. 实现
- 定义和初始化:
int dx[4]={1,0,-1,0};//增量数组
int dy[4]={0,1,0,-1};//增量数组
int a[10][10];
int book[10][10][8];
int n,m;
int sx,sy;
int ans=0x7fffffff;
memset(book,0x3f,sizeof(book));
- 输入(夹带搜索出起点)
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)
sx=i,sy=j;
}
- 进行\(DFS\)
(1) 设置终止条件
if(a[x][y]==3)
{
ans=step;
return;
}
(2) 进行搜索
if(a[x][y]==4)
hp=6;
if(hp<=1 || step>=ans || a[x][y]==0 || step>=book[x][y][hp])
return;
book[x][y][hp]=step;
for(int i=0;i<4;i++)
{
int nx=x+dx[i];
int ny=y+dy[i];
dfs(nx,ny,step+1,hp-1);
}
return;
- 输出
if(ans<0x7ffffff)
cout<<ans;
else
cout<<"-1";
3. 整体代码
#include <bits/stdc++.h>
using namespace std;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int a[10][10];
int book[10][10][8];
int n,m;
int sx,sy;
int ans=0x7fffffff;
void dfs(int x,int y,int step,int hp)
{
if(a[x][y]==3)
{
ans=step;
return;
}
if(a[x][y]==4)
hp=6;
if(hp<=1 || step>=ans || a[x][y]==0 || step>=book[x][y][hp])
return;
book[x][y][hp]=step;
for(int i=0;i<4;i++)
{
int nx=x+dx[i];
int ny=y+dy[i];
dfs(nx,ny,step+1,hp-1);
}
return;
}
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)
sx=i,sy=j;
}
memset(book,0x3f,sizeof(book));
dfs(sx,sy,0,6);
if(ans<0x7ffffff)
cout<<ans;
else
cout<<"-1";
return 0;
}