4635: 【搜索】【广度优先】回家

题目描述

小 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，否则输出他回家所需最短时间。

样例输入

3 3
2 1 1
1 1 0
1 1 3

样例输出

4

Code:

#include<bits/stdc++.h>
using namespace std;
struct node{int x,y,t,r;
}na[15*15];
int n,m,ans=-1,a[15][15];
int sx,sy,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
bool vis[15][15][10];
queue<node>que;
void bfs(){node temp={sx,sy,0,6};que.push(temp);vis[sx][sy][6]=1;while(!que.empty()){node now=que.front();que.pop();if(a[now.x][now.y]==3&&now.r){ans=now.t;return;}for(int i=0;i<4;i++){int xx=now.x+dx[i];int yy=now.y+dy[i];int tt=now.t+1;int rr=now.r-1;if(a[xx][yy]!=0&&!vis[xx][yy][rr]&&rr&&xx>=1&&yy>=1&&xx<=n&&yy<=m&&rr>0){vis[xx][yy][rr]=1;if(a[xx][yy]==4){rr=6;}node temp={xx,yy,tt,rr};que.push(temp);}}} 
}
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;}}}bfs();cout<<ans;return 0;
}