题面描述:

在这个问题中，小塔发现他的房间里进水了，水位不断上涨。他需要通过一些没有被水淹没的箱子移动，以安全地到达电源处。每个小方格的水位上升与箱子的高度有关，只有当水位低于箱子高度时，小塔才能通过该格。输入给出初始水深、房间的格局以及小塔和电源的位置，输出则是小塔从起点到电源的路径长度和每一步的位置坐标。如果无法到达电源，小塔则留在原地。通过这个问题，我们可以帮助小塔设计一条安全的路线，以确保他能顺利关闭电源。

思路:高维bfs

考虑记录状态:(x,y,step) 代表在位置x,y并且已经走了step步状态下是否合法。

$fa[x][y][step]$ 记录这个状态下的上一步是哪里来的。

然后直接进行bfs,过程中注意放进队列之前判断step + init_h 以及 $a[i][j]$ 之间的大小关系。

最后需要bfs输出路径

问题描述

小塔的房间为一个矩形网格，水位不断上涨。每个小方格可能放有箱子，不同高度的箱子会影响水位的淹没速度。小塔每单位时间只能移动到相邻的方格，并且只能在未被水淹没的方格中行走。我们的目标是帮助小塔找到一条从起点（标记为s）到终点（标记为t）的安全路径。如果没有这样的路径，则小塔需要留在原地。

状态记录

我们使用状态 (x, y, step) 来表示小塔在位置 (x, y)，并且已经走了 step 步。为了追踪路径，我们定义了一个三维数组 fa[x][y][step] 来记录在状态 (x, y, step) 下的上一步来自哪里。这有助于在找到终点后，能够回溯出完整的路径。

BFS算法实现

1. 初始化：

   • 读取初始水深、房间的大小以及地图的布局。
   • 找到起点和终点的位置。
   • 初始化队列，存储起点和初始高度，同时创建 fa 数组来记录状态。

2. 方向数组：

   • 定义四个方向（上、下、左、右）的移动方式。

3. BFS过程：

   • 从队列中取出当前状态 (x, y, h)。
   • 检查是否到达终点。如果到达，则记录结果并退出。
   • 遍历四个可能的移动方向，计算新位置 (nx, ny) 及新高度 nh。
   • 检查新位置是否越界、是否是起点或是否已经访问过。
   • 如果新位置是一个箱子，则获取其高度；如果不是，则设为一个很大的数。
   • 如果当前水位不够以通过该位置，则继续循环。
   • 如果可以通过，记录状态并将新状态加入队列。

4. 路径回溯：

   • 如果没有找到路径，输出路径长度为 1，坐标为起点。
   • 如果找到路径，从终点回溯到起点，收集路径上的每个坐标并输出。

代码

java

to be fill

python

# 读取初始高度
height = int(input())
# 读取地图的行数和列数
n, m = map(int, input().split())
# 读取地图数据
a = [input().split() for _ in range(n)]

# 初始化起点和终点
sx, sy = 0, 0
ex, ey = 0, 0

# 找到起点 's' 和终点 't' 的坐标
for i in range(n):
    for j in range(m):
        if a[i][j] == "s":
            sx, sy = i, j  # 起点坐标
        if a[i][j] == "t":
            ex, ey = i, j  # 终点坐标

# 队列初始化，包含起点和初始高度
que = [(sx, sy, height)]
# fa 数组记录状态，fa[x][y][step] 记录状态下的上一步位置
fa = [[[-1 for _ in range(n * m)] for _ in range(m)] for _ in range(n)]

# 方向数组，表示上下左右四个方向
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
ok = False  # 路径是否找到的标志
res_h = 0   # 记录找到的高度

# BFS 开始
while que:
    x, y, h = que.pop(0)  # 从队列中取出当前状态
    # 如果到达终点，记录结果并退出
    if x == ex and y == ey:
        res_h = h
        ok = True
        break
    # 遍历四个方向
    for i in range(4):
        nx, ny, nh = x + dx[i], y + dy[i], h + 1  # 新位置和新高度
        # 检查新位置是否越界或是起点，或是状态已访问
        if nx < 0 or nx >= n or ny < 0 or ny >= m or a[nx][ny] == "s" or fa[nx][ny][nh] != -1:
            continue
        now = 0
        # 如果新位置是数字，获取其高度，否则设为一个很大的数
        if a[nx][ny].isdigit():
            now = int(a[nx][ny])
        else:
            now = 10**9
        # 如果当前高度不够，无法通过
        if now <= nh:
            continue
        # 记录状态
        fa[nx][ny][nh] = (x, y)
        # 将新状态加入队列
        que.append((nx, ny, nh))

# 如果未找到路径
if not ok:
    print(1)  # 输出结果
    print(sx, sy)  # 输出起点坐标
else:
    ans = []  # 存储路径
    x, y, h = ex, ey, res_h  # 从终点开始回溯
    while x != sx or y != sy:  # 回溯到起点
        ans.append((x, y))  # 记录路径
        x, y = fa[x][y][h]  # 获取上一步的位置
        h -= 1  # 高度减一
    ans.append((sx, sy))  # 添加起点到路径
    ans.reverse()  # 反转路径

    # 输出路径长度和路径坐标
    print(len(ans))
    for x, y in ans:
        print(x, y)

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>  // 添加这一行以使用 reverse 函数

using namespace std;

int main() {
    // 读取初始高度
    int height;
    cin >> height;

    // 读取地图的行数和列数
    int n, m;
    cin >> n >> m;

    // 读取地图数据
    vector<vector<string>> a(n, vector<string>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    // 初始化起点和终点
    int sx = -1, sy = -1, ex = -1, ey = -1;

    // 找到起点 's' 和终点 't' 的坐标
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == "s") {
                sx = i;
                sy = j;  // 起点坐标
            }
            if (a[i][j] == "t") {
                ex = i;
                ey = j;  // 终点坐标
            }
        }
    }

    // 检查是否找到了起点和终点
    if (sx == -1 || sy == -1 || ex == -1 || ey == -1) {
        cout << "Error: Start or end point not found." << endl;
        return 1;
    }

    // 队列初始化，包含起点和初始高度
    queue<tuple<int, int, int>> que;
    que.push(make_tuple(sx, sy, height));

    // fa 数组记录状态，fa[x][y][step] 记录状态下的上一步位置
    vector<vector<vector<int>>> fa(n, vector<vector<int>>(m, vector<int>(n * m, -1)));

    // 方向数组，表示上下左右四个方向
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

    bool ok = false;  // 路径是否找到的标志
    int res_h = 0;    // 记录找到的高度

    // BFS 开始
    while (!que.empty()) {
        auto [x, y, h] = que.front();  // 从队列中取出当前状态
        que.pop();  // 出队

        // 如果到达终点，记录结果并退出
        if (x == ex && y == ey) {
            res_h = h;
            ok = true;
            break;
        }

        // 遍历四个方向
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i], nh = h + 1;  // 新位置和新高度
            
            // 检查新位置是否越界或是起点，或是状态已访问
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || a[nx][ny] == "s" || fa[nx][ny][nh] != -1) {
                continue;
            }

            int now = 0;
            // 如果新位置是数字，获取其高度，否则设为一个很大的数
            if (isdigit(a[nx][ny][0])) {
                now = stoi(a[nx][ny]);
            } else {
                now = 10 * 9; // 设为一个很大的数
            }

            // 如果当前高度不够，无法通过
            if (now <= nh) {
                continue;
            }

            // 记录状态
            fa[nx][ny][nh] = x * m + y; // 记录上一步位置（转换为一维表示）
            // 将新状态加入队列
            que.push(make_tuple(nx, ny, nh));
        }
    }

    // 如果未找到路径
    if (!ok) {
        cout << 1 << endl;  // 输出结果
        cout << sx << " " << sy << endl;  // 输出起点坐标
    } else {
        vector<pair<int, int>> ans;  // 存储路径
        int x = ex, y = ey, h = res_h;  // 从终点开始回溯
        while (x != sx || y != sy) {  // 回溯到起点
            ans.emplace_back(x, y);  // 记录路径
            int prev = fa[x][y][h];   // 获取上一步的位置
            x = prev / m; // 行坐标
            y = prev % m; // 列坐标
            h--;  // 高度减一
        }
        ans.emplace_back(sx, sy);  // 添加起点到路径

        reverse(ans.begin(), ans.end());  // 反转路径

        // 输出路径长度和路径坐标
        cout << ans.size() << endl;
        for (const auto &p : ans) {
            cout << p.first << " " << p.second << endl;
        }
    }

    return 0;
}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

小明正值班，突然发现他所在的屋子进水了，水面一直上涨，考虑到可能有电器暴露在水中，小明想通过尚未被水淹没的箱子达到电源处，关闭电源。假设电源和小明所处的位置都比较安全，不会被水淹没。已知屋子为矩形，可划分为大小相当的小方格，小明的位置，电源，箱子都正好在小方格的正中间，覆盖整个方格；小明每单位时间可以从一个小方格移动到相邻的处在同一行或者同一列的另一小方格。为了安全小明只能移动到没有被上涨的水面淹没的小方格，箱子的高度不一，所在方格被水淹没的时间取决于方格内箱子的高度

水面每单位时间上涨$1$，如果此时箱子的高度小于或者等于水面的高度，则被淹没。

请帮小明设计一条路线到达电源处，如果没有这样的路线，则小明应该待在原地。

输入描述

第一行：开始时水的深度

第二行：用空格隔开的两个数字，第一个为屋子的长，对应余下输入的行数，第二个为屋子的宽，对应余下输入各行和个数

从第三行开始，描述屋子内小方格的布局。用非$0$数字代表箱子的高度，$0$代表没有箱子，$s$代表小明的位置，t代表电源位置

输出描述

第一行输出一个$m$ , 代表路径长度

接下来$m$ 行，每行一个坐标$(x_i,y_i)$ 代表第$i$步的位置

样例1

输入

0
4 4
s 1 3 5
2 3 2 4
2 4 4 5
3 5 5 t

输出

1
0 0

说明

无法安全到达电源位置，只能呆在原地$s$所在位置

样例2

输入

0
4 4
s 1 2 5
2 3 2 4
2 4 4 5
3 5 7 t

输出

7
0 0
1 0
1 1
2 1
3 1
3 2
3 3

说明

输入：第一行表示开始水面深度为$0$，第二行表示屋子为$4*4$的方格；如果方格坐标从$1$开始，则小明在第$1$行第$1$列，电源在第$4$行第$4$列；

输出：输出了从小明所在位置$s$到电源所在位置$t$以及路径上的箱子高度

注意:如果有多个方案，输出任意一个合法的移动方案即可。