做網(wǎng)站完整視頻重慶seo博客
題目描述
小 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;
}