题目描述

小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:

3 3
2 1 1
1 1 0
1 1 3
输出样例#1:

4

说明

1<=n,m<=9

 //一道挺水的题。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
int n,m,map[][],nx,ny,ans=;
bool a[][];
void dfs(int x,int y,int b,int s){//坐标,血,次数
b--;
if(x==||y==||x>n||y>m||map[x][y]==||a[x][y]||b==||s>ans)//出界,障碍,搜过,死亡,大于答案都要结束
return;
if(map[x][y]==){//记录答案
ans=min(ans,s);
return;
}
if(map[x][y]==)//鼠标
b=;
s++;
a[x][y]=;
dfs(x+,y,b,s);//}
dfs(x,y+,b,s);//|}
dfs(x-,y,b,s);//|}向四周搜
dfs(x,y-,b,s);//}
a[x][y]=;
}
int main(){
int i,j;
cin>>n>>m;
for(i=;i<=n;i++)
for(j=;j<=m;j++){
cin>>map[i][j];
if(map[i][j]==){//记录起点
nx=i;
ny=j;
}
}
dfs(nx,ny,,);//开搜,从起点,
if(ans==)//一开始设的是200,如果没变,说明没结果,则输出-1(有点危险,再大点更好,int最大2147483647)
cout<<-;
else
cout<<ans;
return ;
}
05-11 09:25