題目描述

小 H 在一個劃分成了n×m?個方格的長方形封鎖線上。 每次他能向上下左右四個方向移動一格（當(dāng)然小 H 不可以靜止不動）， 但不能離開封鎖線，否則就被打死了。 剛開始時他有滿血?6 點，每移動一格他要消耗?1 點血量。一旦小 H 的血量降到?0， 他將死去。 他可以沿路通過拾取鼠標（什么鬼。。。）來補滿血量。只要他走到有鼠標的格子，他不需要任何時間即可拾取。格子上的鼠標可以瞬間補滿，所以每次經(jīng)過這個格子都有鼠標。就算到了某個有鼠標的格子才死去， 他也不能通過拾取鼠標補滿 HP。 即使在家門口死去， 他也不能算完成任務(wù)回到家中。

地圖上有五種格子：

0：障礙物。

1：空地， 小 H 可以自由行走。

2：小 H 出發(fā)點， 也是一片空地。

3：小 H 的家。

4：有鼠標在上面的空地。

小 H 能否安全回家？如果能， 最短需要多長時間呢？

輸入

第一行兩個整數(shù)?n,m， 表示地圖的大小為n×m。

下面?n 行， 每行?m 個數(shù)字來描述地圖。

輸出

一行， 若小 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;
}