REALHW92 晶体能量阱储量计算

题目链接

晶体能量阱储量计算

题目描述

给定一个 $H \times W$ 的晶体矩阵 $V$ ，其中 $V(r, c)$ 代表坐标 $(r, c)$ 处的势能。矩阵外部空间势能恒为 0。

对于晶体中的任意一点 $(r, c)$ ，其逃逸势能 $E_{\text{escape}}(r, c)$ 定义为从该点移动到晶体外部的所有可能路径中，路径上遇到的最高势能的最小值。

该点能够存储的能量为： $E_{\text{stored}}(r, c) = \max(0, E_{\text{escape}}(r, c) - V(r, c))$ 。

任务是计算整个晶体能够存储的总能量，即所有能量阱存储能量的总和。

解题思路

这个问题是经典的“接雨水”问题的二维版本。核心任务是为矩阵中的每一个点 $(r, c)$ 计算其逃逸势能 $E_{\text{escape}}(r, c)$ 。这个逃逸势能实际上就是包围点 $(r, c)$ 的“堤坝”的最低高度。

我们可以将这个问题建模为从矩阵的所有边界点出发，向内部寻找最短路径的问题。这里的“路径长度”被重新定义为路径上遇到的最大势能。由于我们想找到这个最大势能的最小值，这与 Dijkstra 算法 的思想完全吻合。

1. 算法建模

图的节点：矩阵中的每个单元格 $(r, c)$ 都是图中的一个节点。
路径成本：从一个节点移动到相邻节点，路径的成本（或称“高度”）是新节点的势能与当前路径高度的较大值。
目标：为每个节点找到一条通往任意边界点的路径，使得这条路径上的最大势能（即路径成本）最小。

2. Dijkstra 算法的应用

逃逸势能数组: 创建一个与输入矩阵大小相同的二维数组 escape_energies[H][W]，用于存储每个点的最小逃逸势能。所有位置的初始值设为无穷大。
优先队列 (Min-Heap): 使用一个最小优先队列来高效地找到当前拥有最低逃逸势能的节点。队列中存储 (energy, r, c) 形式的元组，表示当前已知的、到达 $(r, c)$ 的最低逃逸势能是 energy。
初始化:
- 将所有边界点作为 Dijkstra 算法的初始源。
- 遍历矩阵的第一行、最后一行、第一列和最后一列。
- 对于每个边界点 $(br, bc)$ ，它到边界的路径就是它自身，所以它的逃逸势能就是它自己的势能 $V(br, bc)$ 。
- 更新 escape_energies[br][bc] = V(br, bc)，并将 (V(br, bc), br, bc) 压入优先队列。
主循环:
- 从优先队列中弹出拥有最小 energy 的节点 (current_energy, r, c)。
- 如果 current_energy 大于 escape_energies[r][c] 中已记录的值，说明已经有一条更优的路径（更低的“堤坝”）到达该点，跳过。
- 遍历该节点的四个邻居 (nr, nc)。
- 对于每个邻居，计算通过当前节点 $(r, c)$ 到达它所需的逃逸势能：new_escape_energy = max(current_energy, V(nr, nc))。这可以理解为，水流从 $(r, c)$ 漫延到 $(nr, nc)$ ，新的水位高度由当前水位和邻居的地面高度共同决定，取其较高者。
- 如果 new_escape_energy 小于 escape_energies[nr][nc] 中记录的值，说明我们找到了一个更低的“堤坝”来包围 $(nr, nc)$ 。更新 escape_energies[nr][nc] = new_escape_energy，并将新状态 (new_escape_energy, nr, nc) 压入队列。

3. 计算总能量

Dijkstra 算法结束后，escape_energies 数组就包含了每个点的最小逃逸势能。
遍历整个矩阵，对每个点 $(r, c)$ ，计算其可存储的能量：stored_energy = escape_energies[r][c] - V(r, c)。
将所有点的 stored_energy (如果大于0) 累加起来，就是最终的总能量。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

const long long INF = numeric_limits<long long>::max();

struct State {
    long long energy;
    int r, c;

    bool operator>(const State& other) const {
        return energy > other.energy;
    }
};

int main() {
    int w, h;
    cin >> w >> h;

    vector<vector<int>> matrix(h, vector<int>(w));
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> matrix[i][j];
        }
    }

    vector<vector<long long>> escape_energies(h, vector<long long>(w, INF));
    priority_queue<State, vector<State>, greater<State>> pq;

    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (i == 0 || i == h - 1 || j == 0 || j == w - 1) {
                long long initial_energy = max(0LL, (long long)matrix[i][j]);
                escape_energies[i][j] = initial_energy;
                pq.push({initial_energy, i, j});
            }
        }
    }

    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    while (!pq.empty()) {
        State current = pq.top();
        pq.pop();

        long long current_energy = current.energy;
        int r = current.r;
        int c = current.c;

        if (current_energy > escape_energies[r][c]) {
            continue;
        }

        for (int i = 0; i < 4; ++i) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if (nr >= 0 && nr < h && nc >= 0 && nc < w) {
                long long new_energy = max(current_energy, (long long)matrix[nr][nc]);
                if (new_energy < escape_energies[nr][nc]) {
                    escape_energies[nr][nc] = new_energy;
                    pq.push({new_energy, nr, nc});
                }
            }
        }
    }

    long long total_stored_energy = 0;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            long long stored = escape_energies[i][j] - matrix[i][j];
            if (stored > 0) {
                total_stored_energy += stored;
            }
        }
    }

    cout << total_stored_energy << endl;

    return 0;
}

import java.util.*;

public class Main {
    static class State implements Comparable<State> {
        long energy;
        int r, c;

        public State(long energy, int r, int c) {
            this.energy = energy;
            this.r = r;
            this.c = c;
        }

        @Override
        public int compareTo(State other) {
            return Long.compare(this.energy, other.energy);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int w = sc.nextInt();
        int h = sc.nextInt();

        int[][] matrix = new int[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }

        long[][] escapeEnergies = new long[h][w];
        for (long[] row : escapeEnergies) {
            Arrays.fill(row, Long.MAX_VALUE);
        }

        PriorityQueue<State> pq = new PriorityQueue<>();

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (i == 0 || i == h - 1 || j == 0 || j == w - 1) {
                    long initial_energy = Math.max(0, matrix[i][j]);
                    escapeEnergies[i][j] = initial_energy;
                    pq.offer(new State(initial_energy, i, j));
                }
            }
        }

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        while (!pq.isEmpty()) {
            State current = pq.poll();
            long currentEnergy = current.energy;
            int r = current.r;
            int c = current.c;

            if (currentEnergy > escapeEnergies[r][c]) {
                continue;
            }

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr >= 0 && nr < h && nc >= 0 && nc < w) {
                    long newEnergy = Math.max(currentEnergy, matrix[nr][nc]);
                    if (newEnergy < escapeEnergies[nr][nc]) {
                        escapeEnergies[nr][nc] = newEnergy;
                        pq.offer(new State(newEnergy, nr, nc));
                    }
                }
            }
        }

        long totalStoredEnergy = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                long stored = escapeEnergies[i][j] - matrix[i][j];
                if (stored > 0) {
                    totalStoredEnergy += stored;
                }
            }
        }

        System.out.println(totalStoredEnergy);
    }
}

import heapq

def solve():
    w, h = map(int, input().split())
    matrix = [list(map(int, input().split())) for _ in range(h)]

    escape_energies = [[float('inf')] * w for _ in range(h)]
    pq = []

    for r in range(h):
        for c in range(w):
            if r == 0 or r == h - 1 or c == 0 or c == w - 1:
                energy = max(0, matrix[r][c])
                escape_energies[r][c] = energy
                heapq.heappush(pq, (energy, r, c))
    
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]

    while pq:
        current_energy, r, c = heapq.heappop(pq)

        if current_energy > escape_energies[r][c]:
            continue

        for i in range(4):
            nr, nc = r + dr[i], c + dc[i]
            
            if 0 <= nr < h and 0 <= nc < w:
                new_energy = max(current_energy, matrix[nr][nc])
                if new_energy < escape_energies[nr][nc]:
                    escape_energies[nr][nc] = new_energy
                    heapq.heappush(pq, (new_energy, nr, nc))

    total_stored_energy = 0
    for r in range(h):
        for c in range(w):
            stored = escape_energies[r][c] - matrix[r][c]
            if stored > 0:
                total_stored_energy += stored
    
    print(total_stored_energy)

solve()

算法及复杂度

算法: Dijkstra 算法
时间复杂度: $O(H \cdot W \log(H \cdot W))$ 。在网格图中，节点数 $V = H \cdot W$ ，边数 $E$ 最多为 $4 \cdot H \cdot W$ 。使用二叉堆实现的优先队列，Dijkstra 算法的时间复杂度为 $O(E \log V)$ ，代入后得到 $O(H \cdot W \log(H \cdot W))$ 。
空间复杂度: $O(H \cdot W)$ 。主要用于存储 escape_energies 数组，以及在最坏情况下优先队列可能存储所有节点。

题解 | #晶体能量阱储量计算#