DFS 深搜

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNextLine()){
            int start = Integer.parseInt(in.nextLine());
            String[] strs = in.nextLine().split(" ");
            int len = Integer.parseInt(strs[0]);
            int wid = Integer.parseInt(strs[1]);
            int[][] matrix = new int[len][wid];
            for(int i = 0; i < len; i++){
                String line = in.nextLine();
                String[] inputs = line.split(" ");
                for(int j = 0; j < wid; j++){
                    if(inputs[j].equals("s")){
                        matrix[i][j] = -1;
                    } else if(inputs[j].equals("t")){
                        matrix[i][j] = -2;
                    } else {
                        matrix[i][j] = Integer.parseInt(inputs[j]);
                    }
                }
            }
            closeLight(matrix, start);
        }
    }

    private static List<int[]> res = new ArrayList<>();
    private static void closeLight(int[][] matrix, int start){
        int[] startPoint = new int[2];
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                if(matrix[i][j] == -1){
                    startPoint[0] = i;
                    startPoint[1] = j;
                    dfs(matrix, i, j, 0, start, new ArrayList<>());
                    break;
                }
            }
        }
        //如果res为空，则没有抵达重点，则将起点坐标放进去
        if(res.size() == 0){
            res.add(startPoint);
        }
        System.out.println(res.size());
        for(int i = 0; i < res.size(); i++){
            int[] temp = res.get(i);
            System.out.println(temp[0] + " " + temp[1]);
        }
    }

    private static void dfs(int[][] matrix, int row, int col, int time, int start, List<int[]> path){
        //已经有一条路了，停止深搜
        if(res.size() > 0){
            return;
        }
        if((row >= 0 && row < matrix.length && col >= 0 && col < matrix[0].length) || time == 0){
            //到达终点
            if(matrix[row][col] == -2){
                path.add(new int[]{row, col});
                res.addAll(new ArrayList(path));
                return;
            }
            // 水涨上来了
            if (time != 0 && matrix[row][col] <= start + time){
                return;
            } else { // 水没涨上来
                path.add(new int[]{row, col});
                int temp = matrix[row][col];
                matrix[row][col] = 0;
                dfs(matrix, row + 1, col, time + 1, start, path);
                dfs(matrix, row - 1, col, time + 1, start, path);
                dfs(matrix, row, col + 1, time + 1, start, path);
                dfs(matrix, row, col - 1, time + 1, start, path);
                path.remove(path.size() - 1);
                matrix[row][col] = temp;
            }
        }
    }

题面描述:

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

思路:高维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会员可以通过点击题目上方《已通过》查看其他通过代码来学习。