洛谷 P2802 回家
题目链接
https://www.luogu.org/problemnew/show/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,否则输出他回家所需最短时间。
思路
又是一道普及-的搜索回溯题
没血了或者是血的值为0就返回,然后进行搜索和回溯
搜索和回溯中的判断条件:该点未访问过并且该点不是边界(边界即值为零的店)
然后就是将答案定义为最大值,搜到指定点(家)时判断当前步骤是否小于答案(必须是搜到指定点!!!)
最后判断一下ans是否改变过,如果改变过就输出答案,否则输出-1
代码
#include<bits/stdc++.h>//还是懒人头文件
using namespace std; int a[][];//水水的数据
bool vis[][];
int ans=0x3f;
int n,m;
int ix,iy,jx,jy;
int dx[]= {,,,-,};//走上下左右四个点的数组
int dy[]= {,-,,,}; void dfs(int x,int y,int step,int blo) {
if(blo==)return;
if(a[x][y]==)blo=;//碰到鼠标就回满血
if(x==jx&&y==jy) {
if(ans>step)ans=step;
return;
}
for(int i=; i<=; i++) {
int nx=x+dx[i];
int ny=y+dy[i];
if(vis[nx][ny]==&&a[nx][ny]!=) {
vis[nx][ny]=;
dfs(nx,ny,step+,blo-);
vis[nx][ny]=;//回溯
}
}
} int main() {
scanf("%d%d",&n,&m);
for(int i=; i<=n; i++) {
for(int j=; j<=m; j++) {
scanf("%d",&a[i][j]);
if(a[i][j]==) {
ix=i,iy=j;//起点坐标
a[i][j]=;
}
if(a[i][j]==) {
jx=i,jy=j;//终点坐标
a[i][j]=;
}
}
}
dfs(ix,iy,,);
if(ans!=0x3f)cout<<ans;
else cout<<-;
return ;
}