简简单单
2024-07-02 17:32:30
发布于:广东
7阅读
0回复
0点赞
这个问题可以通过使用广度优先搜索(BFS)来解决,因为我们需要找到最短路径。以下是解决问题的步骤和代码实现:
地图表示:使用二维数组来表示地图,其中不同的数字代表不同的含义:
0 表示障碍物,不能通行。
1 表示空地,可以自由行走。
2 表示小 H 的出发点。
3 表示小 H 的家。
4 表示有鼠标的空地,可以补充小 H 的血量。
BFS搜索:从小 H 的出发点开始进行BFS,尝试找到一条从出发点到家的最短路径。在BFS过程中,每次移动到一个新的位置时,需要考虑以下几点:
是否超出地图边界。
是否是障碍物。
是否已经访问过(避免重复访问)。
血量管理:每移动一步,小 H 的血量减少1点。如果移动到有鼠标的格子,则可以补充到满血量(6点)。
终止条件:如果BFS完成后,能够到达小 H 的家,则输出路径长度;否则输出 -1。
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int MAXN = 9;
const int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向
struct Point {
int x, y;
int health;
int steps;
Point(int _x, int _y, int _health, int _steps) : x(_x), y(_y), health(_health), steps(_steps) {}
};
int n, m;
vector<vector<int>> grid;
vector<vector<bool>> visited;
bool isValid(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m;
}
int bfs(int start_x, int start_y) {
queue<Point> q;
q.push(Point(start_x, start_y, 6, 0));
visited[start_x][start_y] = true;
while (!q.empty()) {
Point cur = q.front();
q.pop();
// 到达家
if (grid[cur.x][cur.y] == 3) {
return cur.steps;
}
// 尝试四个方向移动
for (int d = 0; d < 4; ++d) {
int nx = cur.x + dir[d][0];
int ny = cur.y + dir[d][1];
if (isValid(nx, ny) && !visited[nx][ny]) {
if (grid[nx][ny] == 0) continue; // 障碍物
if (grid[nx][ny] == 4) { // 有鼠标的格子
q.push(Point(nx, ny, 6, cur.steps + 1));
visited[nx][ny] = true;
} else {
if (cur.health > 1) {
q.push(Point(nx, ny, cur.health - 1, cur.steps + 1));
visited[nx][ny] = true;
}
}
}
}
}
return -1; // 无法到达家
}
int main() {
cin >> n >> m;
grid.resize(n, vector<int>(m));
visited.resize(n, vector<bool>(m, false));
int start_x, start_y;
// 读取地图信息
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> grid[i][j];
if (grid[i][j] == 2) {
start_x = i;
start_y = j;
}
}
}
int result = bfs(start_x, start_y);
cout << result << endl;
return 0;
}
这里空空如也
有帮助,赞一个