洛谷P2802 回家
题目描述
小 H 在一个划分成了 n×m 个方格的长方形封锁线上。 每次他能向上下左右四个方向移动一格(当然小 H 不可以静止不动), 但不能离开封锁线,否则就被打死了。 刚开始时他有满血 6 点,每移动一格他要消耗 1 点血量。一旦小 H 的血量降到 0, 他将死去。 他可以沿路通过拾取鼠标来补满血量。只要他走到有鼠标的格子,他不需要任何时间即可拾取。格子上的鼠标可以瞬间补满,所以每次经过这个格子都有鼠标。就算到了某个有鼠标的格子才死去, 他也不能通过拾取鼠标补满 HP。 即使在家门口死去, 他也不能算完成任务回到家中。
地图上有五种格子:
0:障碍物。
1:空地, 小 H 可以自由行走。
2:小 H 出发点, 也是一片空地。
3:小 H 的家。
4:有鼠标在上面的空地。
小 H 能否安全回家?如果能, 最短需要多长时间呢?
输入格式
第一行两个整数 n,m, 表示地图的大小为 n×m 。
下面 n 行, 每行 m 个数字来描述地图。
输出格式
一行, 若小 H 不能回家, 输出 -1,否则输出他回家所需最短时间。
样例 #1
样例输入 #1
3 3
2 1 1
1 1 0
1 1 3
样例输出 #1
4
提示
对于所有数据,1≤n,m≤9。
2021.9.2 增添一组 hack 数据 by @囧仙
#include
using namespace std;
struct pl
{
int kinds,hp,step;
bool arrive;
};
int m,n,jx,jy;
pl num[11][11];
void search(int s)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(num[i][j].hp>1)
{
if(num[i+1][j].hp>num[i][j].hp-1&&num[i+1][j].kinds!=0)
{
if(num[i+1][j].kinds==4)
num[i+1][j].hp=6;
else
num[i+1][j].hp=num[i][j].hp-1;
}
if((num[i+1][j].step==-1||num[i+1][j].step>num[i][j].step+1)&&num[i+1][j].kinds!=0)
{
num[i+1][j].step=num[i][j].step+1;
num[i+1][j].arrive=true;
}
if(num[i-1][j].hp>num[i][j].hp-1&&num[i-1][j].kinds!=0)
{
if(num[i-1][j].kinds==4)
num[i-1][j].hp=6;
else
num[i-1][j].hp=num[i][j].hp-1;
}
if((num[i-1][j].step==-1||num[i-1][j].step>num[i][j].step+1)&&num[i-1][j].kinds!=0)
{
num[i-1][j].step=num[i][j].step+1;
num[i-1][j].arrive=true;
}
if(num[i][j+1].hp>num[i][j].hp-1&&num[i][j+1].kinds!=0)
{
if(num[i][j+1].kinds==4)
num[i][j+1].hp=6;
else
num[i][j+1].hp=num[i][j].hp-1;
}
if((num[i][j+1].step==-1||num[i][j+1].step>num[i][j].step+1)&&num[i][j+1].kinds!=0)
{
num[i][j+1].step=num[i][j].step+1;
num[i][j+1].arrive=true;
}
if(num[i][j-1].hp>num[i][j].hp-1&&num[i][j-1].kinds!=0)
{
if(num[i][j-1].kinds==4)
num[i][j-1].hp=6;
else
num[i][j-1].hp=num[i][j].hp-1;
}
if((num[i][j-1].step==-1||num[i][j-1].step>num[i][j].step+1)&&num[i][j-1].kinds!=0)
{
num[i][j-1].step=num[i][j].step+1;
num[i][j-1].arrive=true;
}
}
}
}
if(s=n*m*100)
return;
else
search(s+1);
}
int main()
{
for(int i=0;i<11;i++)
{
for(int j=0;j<11;j++)
{
num[i][j].arrive=false;
num[i][j].hp=-1;
num[i][j].kinds=0;
num[i][j].step=-1;
}
}
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>num[i][j].kinds;
if(num[i][j].kinds==2)
{
num[i][j].hp=6;
num[i][j].step=0;
num[i][j].arrive=true;
}
if(num[i][j].kinds==3)
{
jx=i;
jy=j;
}
}
}
search(0);
cout<[jx][jy].step;
}
一直是-1,我也是醉了。