地下探险

题意

给定一个 的地下迷宫网格，每个格子有三种状态： 表示可通行， 表示墙壁（不可通行）， 表示氧气补给站。探险者从起点 出发，要到达终点 ，每一步可以向上下左右四个方向移动一格。探险者携带的氧气最多支持连续行走 步，每走一步消耗一单位氧气；当踏上氧气补给站时，氧气自动补满为 。求从起点到终点的最短步数，若无法到达输出 。

思路

乍一看像普通的 BFS 最短路，但多了一个「氧气」约束——走 步后如果没碰到补给站就走不动了。这意味着什么？

同一个格子，带着不同的剩余氧气量到达，后续的可达范围完全不同。比如你带着 单位氧气到达某格，和带着 单位氧气到达同一格，前者能走的路远得多。所以不能只用格子坐标来去重，还需要把剩余氧气作为状态的一部分。

状态定义为 ，其中 是当前格子， 是剩余氧气量。BFS 搜索这个二维状态空间，第一次到达终点时就是最短路径。

转移规则也很清晰：

  • 从 往相邻格 走一步，消耗一单位氧气
  • 如果 ，走不了
  • 如果 是墙壁（值为 ），走不了
  • 如果 是补给站（值为 ），到达后氧气重置为
  • 否则到达后氧气为

那状态空间有多大？，最坏情况可能很大。能不能剪枝？

关键观察：对于同一个格子，到达时氧气越多越好。如果我们之前已经带着 单位氧气到达了格子 ，现在又带着 单位到达，后者完全被前者「支配」——前者能做到的，后者都能做到，而且不会更晚（BFS 按层扩展，距离是非递减的）。

所以我们维护一个数组 ，记录到达每个格子时见过的最大氧气量。只有当新状态的氧气严格大于 时，才有必要入队。这个剪枝在实际测试中非常有效，能大幅减少状态数。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    int M, N;
    scanf("%d%d", &M, &N);
    int MN = M * N;
    vector<int> grid(MN);
    for(int i = 0; i < MN; i++) scanf("%d", &grid[i]);
    int sr, sc, er, ec, K;
    scanf("%d%d%d%d%d", &sr, &sc, &er, &ec, &K);

    if(sr == er && sc == ec){
        puts("0");
        return 0;
    }

    int startCell = sr * N + sc;
    int endCell = er * N + ec;

    vector<int> maxOxy(MN, -1);

    struct State { int cell, oxy, dist; };
    queue<State> q;
    maxOxy[startCell] = K;
    q.push({startCell, K, 0});

    while(!q.empty()){
        State s = q.front(); q.pop();
        int cell = s.cell, oxy = s.oxy, d = s.dist;
        if(cell == endCell){
            printf("%d\n", d);
            return 0;
        }
        if(oxy < maxOxy[cell]) continue;
        if(oxy == 0) continue;

        int r = cell / N, c = cell % N;
        int nb[4]; int cnt = 0;
        if(r > 0) nb[cnt++] = cell - N;
        if(r < M-1) nb[cnt++] = cell + N;
        if(c > 0) nb[cnt++] = cell - 1;
        if(c < N-1) nb[cnt++] = cell + 1;

        for(int i = 0; i < cnt; i++){
            int nc = nb[i];
            if(grid[nc] == 1) continue;
            int noxy = (grid[nc] == 2) ? K : oxy - 1;
            if(noxy > maxOxy[nc]){
                maxOxy[nc] = noxy;
                q.push({nc, noxy, d + 1});
            }
        }
    }
    puts("-1");
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer st = new StreamTokenizer(br);

        st.nextToken(); int M = (int) st.nval;
        st.nextToken(); int N = (int) st.nval;
        int MN = M * N;
        int[] grid = new int[MN];
        for (int i = 0; i < MN; i++) {
            st.nextToken();
            grid[i] = (int) st.nval;
        }
        st.nextToken(); int sr = (int) st.nval;
        st.nextToken(); int sc = (int) st.nval;
        st.nextToken(); int er = (int) st.nval;
        st.nextToken(); int ec = (int) st.nval;
        st.nextToken(); int K = (int) st.nval;

        if (sr == er && sc == ec) {
            System.out.println(0);
            return;
        }

        int startCell = sr * N + sc;
        int endCell = er * N + ec;

        int[] maxOxy = new int[MN];
        Arrays.fill(maxOxy, -1);

        Deque<int[]> q = new ArrayDeque<>();
        maxOxy[startCell] = K;
        q.add(new int[]{startCell, K, 0});

        while (!q.isEmpty()) {
            int[] s = q.poll();
            int cell = s[0], oxy = s[1], d = s[2];
            if (cell == endCell) {
                System.out.println(d);
                return;
            }
            if (oxy < maxOxy[cell]) continue;
            if (oxy == 0) continue;

            int r = cell / N, c = cell % N;
            if (r > 0 && grid[cell - N] != 1) {
                int nc = cell - N;
                int noxy = (grid[nc] == 2) ? K : oxy - 1;
                if (noxy > maxOxy[nc]) { maxOxy[nc] = noxy; q.add(new int[]{nc, noxy, d + 1}); }
            }
            if (r < M - 1 && grid[cell + N] != 1) {
                int nc = cell + N;
                int noxy = (grid[nc] == 2) ? K : oxy - 1;
                if (noxy > maxOxy[nc]) { maxOxy[nc] = noxy; q.add(new int[]{nc, noxy, d + 1}); }
            }
            if (c > 0 && grid[cell - 1] != 1) {
                int nc = cell - 1;
                int noxy = (grid[nc] == 2) ? K : oxy - 1;
                if (noxy > maxOxy[nc]) { maxOxy[nc] = noxy; q.add(new int[]{nc, noxy, d + 1}); }
            }
            if (c < N - 1 && grid[cell + 1] != 1) {
                int nc = cell + 1;
                int noxy = (grid[nc] == 2) ? K : oxy - 1;
                if (noxy > maxOxy[nc]) { maxOxy[nc] = noxy; q.add(new int[]{nc, noxy, d + 1}); }
            }
        }
        System.out.println(-1);
    }
}

import sys
from collections import deque

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    M = int(data[idx]); idx += 1
    N = int(data[idx]); idx += 1
    MN = M * N
    grid = [0] * MN
    for i in range(MN):
        grid[i] = int(data[idx]); idx += 1
    sr = int(data[idx]); idx += 1
    sc = int(data[idx]); idx += 1
    er = int(data[idx]); idx += 1
    ec = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1

    start = sr * N + sc
    end = er * N + ec

    if start == end:
        print(0)
        return

    maxOxy = [-1] * MN
    maxOxy[start] = K
    q = deque()
    q.append((start, K, 0))

    while q:
        cell, oxy, d = q.popleft()
        if cell == end:
            print(d)
            return
        if oxy < maxOxy[cell]:
            continue
        if oxy == 0:
            continue

        r, c = divmod(cell, N)

        for nc in (cell - N if r > 0 else -1,
                   cell + N if r < M - 1 else -1,
                   cell - 1 if c > 0 else -1,
                   cell + 1 if c < N - 1 else -1):
            if nc == -1 or grid[nc] == 1:
                continue
            noxy = K if grid[nc] == 2 else oxy - 1
            if noxy > maxOxy[nc]:
                maxOxy[nc] = noxy
                q.append((nc, noxy, d + 1))

    print(-1)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const tokens = lines.join(' ').split(/\s+/).map(Number);
    let idx = 0;
    const M = tokens[idx++], N = tokens[idx++];
    const MN = M * N;
    const grid = new Int32Array(MN);
    for (let i = 0; i < MN; i++) grid[i] = tokens[idx++];
    const sr = tokens[idx++], sc = tokens[idx++];
    const er = tokens[idx++], ec = tokens[idx++];
    const K = tokens[idx++];

    const start = sr * N + sc;
    const end = er * N + ec;

    if (start === end) {
        console.log(0);
        return;
    }

    const maxOxy = new Int32Array(MN).fill(-1);
    maxOxy[start] = K;

    const q = [[start, K, 0]];
    let head = 0;

    while (head < q.length) {
        const [cell, oxy, d] = q[head++];
        if (cell === end) {
            console.log(d);
            return;
        }
        if (oxy < maxOxy[cell]) continue;
        if (oxy === 0) continue;

        const r = Math.floor(cell / N), c = cell % N;

        const tryMove = (nc) => {
            if (grid[nc] === 1) return;
            const noxy = grid[nc] === 2 ? K : oxy - 1;
            if (noxy > maxOxy[nc]) {
                maxOxy[nc] = noxy;
                q.push([nc, noxy, d + 1]);
            }
        };

        if (r > 0) tryMove(cell - N);
        if (r < M - 1) tryMove(cell + N);
        if (c > 0) tryMove(cell - 1);
        if (c < N - 1) tryMove(cell + 1);
    }
    console.log(-1);
});

复杂度

  • 时间复杂度：，最坏情况下每个格子可能以不同氧气量被访问。实际中 剪枝使得大部分格子只被访问少数几次。
  • 空间复杂度：， 数组和 BFS 队列。