P2802 回家
P2802 回家 - 洛谷
题目描述
小 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，否则输出他回家所需最短时间。
输入输出样例
| 输入 #1 | 输出 #1 |
|---|---|
| 3 3 2 1 1 1 1 0 1 1 3 | 4 |
说明/提示
对于所有数据，1≤n,m≤9。
2021.9.2 增添一组 hack 数据 by @囧仙
思路：
多开一维度储存到达位置的唯一血量路径
代码：
#include<bits/stdc++.h>
using namespace std;int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int n,m,startx,starty,endx,endy;
int G[15][15];
bool vis[15][15][7]; // 三维标记数组，记录在(x,y)位置且血量为hp时是否已经访问过struct Node{int x,y,t,hp; // x,y是坐标，t是时间，hp是当前血量
};int bfs()
{queue<Node> q;memset(vis, false, sizeof(vis));q.push({startx, starty, 0, 6});vis[startx][starty][6] = true;while(!q.empty()) {Node cur = q.front();q.pop();int x = cur.x;int y = cur.y;int t = cur.t;int hp = cur.hp;if(hp <= 0) continue;if(x == endx && y == endy) {return t;}for(int i = 0; i < 4; i++) {int nx = x + dx[i];int ny = y + dy[i];if(nx < 1 || nx > n || ny < 1 || ny > m || G[nx][ny] == 0) continue;int newHp = hp - 1;if(newHp <= 0)continue; if(G[nx][ny] == 4) newHp = 6;if(!vis[nx][ny][newHp]) {vis[nx][ny][newHp] = true;q.push({nx, ny, t + 1, newHp});}}}return -1;
}int main()
{cin >> n >> m;for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++){cin >> G[i][j];if(G[i][j] == 2) {startx = i;starty = j;}if(G[i][j] == 3) {endx = i;endy = j;}}}int ans = bfs();cout << ans << endl;return 0;
}