网站开发详细设计文档,惠州排名推广,seo北京优化,wordpress读者墙插件题目描述
小 H 在一个划分成了nm 个方格的长方形封锁线上。 每次他能向上下左右四个方向移动一格#xff08;当然小 H 不可以静止不动#xff09;#xff0c; 但不能离开封锁线#xff0c;否则就被打死了。 刚开始时他有满血 6 点#xff0c;每移动一格他要消耗 1 点血量…题目描述
小 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:
#includebits/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];
queuenodeque;
void bfs(){node temp{sx,sy,0,6};que.push(temp);vis[sx][sy][6]1;while(!que.empty()){node nowque.front();que.pop();if(a[now.x][now.y]3now.r){ansnow.t;return;}for(int i0;i4;i){int xxnow.xdx[i];int yynow.ydy[i];int ttnow.t1;int rrnow.r-1;if(a[xx][yy]!0!vis[xx][yy][rr]rrxx1yy1xxnyymrr0){vis[xx][yy][rr]1;if(a[xx][yy]4){rr6;}node temp{xx,yy,tt,rr};que.push(temp);}}}
}
int main(){cinnm;for(int i1;in;i){for(int j1;jm;j){cina[i][j];if(a[i][j]2){sxi;syj;}}}bfs();coutans;return 0;
}
