M12029: 水淹七军

bfs, dfs, http://cs101.openjudge.cn/pctbook/M12029/

随着最后通牒的递出，C国的总攻也开始了，由于C国在地形上的优势，C国总司令下令采用水攻，剿灭A国最后的有生力量。地形图是一个M*N的矩阵，矩阵上每一个点都对应着当前点的高度。C国总司令将选择若干个点进行放水。根据水往低处流的特性，水可以往四个方向的流动，被淹的地方的水面高度便和放水点的高度一样。然而，A国不是一马平川的，所以总会有地方是淹没不到的。你的任务很简单，判断一下A国司令部会不会被淹没掉。我们将给你完整的地形图，然后给出A国司令部所在位置，给出C国将在哪几个点进行放水操作。你所需要的，就是给出A国司令部会不会被水淹。

输入

第一行：一个整数K，代表数据组数。对于每一组数据：第1行：符合题目描述的两个整数，M(0 < M <= 200)、N(0 < N <= 200)。第2行至M+1行：每行N个数，以空格分开，代表这个矩阵上的各点的高度值H(0 <= H <= 1000)。第M+2行：两个整数I(0 < I <= M)、J(0 < J <= N)，代表司令部所在位置。第M+3行：一个整数P(0 < P <= M * N)，代表放水点个数。第M+4行至M+P+4行：每行两个整数X(0 < X <= M)、Y(0 < Y <= N)，代表放水点。

输出

对于每组数据，输出一行，如果被淹则输出Yes，没有则输出No。

样例输入

样例输出

No

提示

样例中左上角的位置是(1, 1),右上角的位置是(1, 5), 右下角的位置是(5, 5)

根据样例，可以这样理解：如果司令部与周围水等高，不算淹没。

不用visited的原因，有的点在某些情况下也需要重新遍历。比如之前淹没的高度为h，之后放水的高度H>h，此时就需要重新淹没。即可以不用visited，直接用water_height矩阵（每次洪泛更新），只要扩展点的高度小于当前water_height_value。

bfs实现

python

from collections import deque
import sys
input = sys.stdin.read

# 判断坐标是否有效
def is_valid(x, y, m, n):
    return 0 <= x < m and 0 <= y < n

# 广度优先搜索模拟水流
def bfs(start_x, start_y, start_height, m, n, h, water_height):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    q = deque([(start_x, start_y, start_height)])
    water_height[start_x][start_y] = start_height

    while q:
        x, y, height = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if is_valid(nx, ny, m, n) and h[nx][ny] < height:
                if water_height[nx][ny] < height:
                    water_height[nx][ny] = height
                    q.append((nx, ny, height))

# 主函数
def main():
    data = input().split()  # 快速读取所有输入数据
    idx = 0
    k = int(data[idx])
    idx += 1
    results = []

    for _ in range(k):
        m, n = map(int, data[idx:idx + 2])
        idx += 2
        h = []
        for i in range(m):
            h.append(list(map(int, data[idx:idx + n])))
            idx += n
        water_height = [[0] * n for _ in range(m)]

        i, j = map(int, data[idx:idx + 2])
        idx += 2
        i, j = i - 1, j - 1

        p = int(data[idx])
        idx += 1

        for _ in range(p):
            x, y = map(int, data[idx:idx + 2])
            idx += 2
            x, y = x - 1, y - 1

            bfs(x, y, h[x][y], m, n, h, water_height)

        results.append("Yes" if water_height[i][j] > 0 else "No")

    sys.stdout.write("\n".join(results) + "\n")

if __name__ == "__main__":
    main()

思路是对的，但性能上有一个明显瓶颈：

每一个放水点都单独做一次 BFS，在最坏情况下： $P = M N = 4 \times 10^{4}$ ，每次 BFS 扫全图→ TLE

本质优化版，保持你“water_height 矩阵、不用 visited、可重复淹没”的思想，但把复杂度从 $O (P \cdot M N) \to O (M N \log M N)$

核心优化思路

👉 多源 + 最大堆 BFS（反向 Dijkstra）

每个放水点是一个“水源”，水位 = 该点高度
水只能从 高 → 低 流
对每个点，只需要知道： 它能被淹到的最高水位是多少

这正是一个：在高度约束下，最大化 water_height 的传播问题

标准 AC 解法（推荐）

python

import sys
import heapq

input = sys.stdin.read

def main():
    data = list(map(int, input().split()))
    idx = 0
    K = data[idx]
    idx += 1
    out = []

    for _ in range(K):
        M, N = data[idx], data[idx+1]
        idx += 2

        h = []
        for _ in range(M):
            h.append(data[idx:idx+N])
            idx += N

        I, J = data[idx]-1, data[idx+1]-1
        idx += 2

        P = data[idx]
        idx += 1

        water = [[-1]*N for _ in range(M)]
        pq = []  # max-heap: (-water_height, x, y)

        for _ in range(P):
            x, y = data[idx]-1, data[idx+1]-1
            idx += 2
            w = h[x][y]
            if w > water[x][y]:
                water[x][y] = w
                heapq.heappush(pq, (-w, x, y))

        dx = (-1, 1, 0, 0)
        dy = (0, 0, -1, 1)

        flooded = False

        while pq:
            w, x, y = heapq.heappop(pq)
            w = -w

            if w < water[x][y]:
                continue

            if x == I and y == J and w > h[I][J]:
                flooded = True
                break

            for d in range(4):
                nx, ny = x+dx[d], y+dy[d]
                if 0 <= nx < M and 0 <= ny < N:
                    if h[nx][ny] < w and w > water[nx][ny]:
                        water[nx][ny] = w
                        heapq.heappush(pq, (-w, nx, ny))

        out.append("Yes" if flooded else "No")

    print("\n".join(out))


if __name__ == "__main__":
    main()

复杂度分析

每个点最多被更新几次（堆优化）
总复杂度： $O (M N \log M N)$ ， $200 \times 200$ 轻松过

总结

这是一个多源、单调约束、最大值传播问题用 最大堆 BFS（反向 Dijkstra） 是最自然、最稳妥的解法

代码关键点注释说明：

输入处理：使用 sys.stdin.read().split() 将所有输入读入内存并转为迭代器。这比一行行 input() 读入要快得多，且能很好地处理不同操作系统下的换行符问题。
坐标转换：题目给出的是 1-based（从1开始）的坐标，Python 列表是 0-based（从0开始），所以在读取 $I, J, X, Y$ 时都要减 1。
逆向 BFS：
- 如果我们正向模拟水流（从放水点流向低处），需要对每一个放水点做一次搜索，容易超时。
- 逆向思路：如果水能从 A 流到 B（ $H_{A} \geq \dots \geq H_{B}$ ），那么一定能从 B 逆着走到 A（ $H_{B} \leq \dots \leq H_{A}$ ）。
- 我们只从终点（司令部）出发进行一次 BFS，标记所有能通过“爬山”到达的点。
判定：最后只需 $O (P)$ 的时间遍历一下放水点列表，看有没有放水点落在了我们标记的区域内即可。

python

from collections import deque

for _ in range(int(input())):
    m, n = map(int, input().split())
    # 创建网格，添加边界
    l = [[1000] * (n + 2)]
    for i in range(m):
        l.append([1000] + list(map(int, input().split())) + [1000])
    l.append([1000] * (n + 2))
    I, J = map(int, input().split())
    P = int(input())

    found = False
    for i in range(P):
        x, y = map(int, input().split())
        # 如果已经找到，跳过后续放水点
        if found:
            continue
        use = [[0] * (n + 2) for j in range(m + 2)]
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        # BFS队列
        queue = deque()
        # 标记起始点并加入队列
        use[x][y] = 1
        queue.append((x, y))
        h = l[x][y]  # 放水点高度

        while queue:
            cx, cy = queue.popleft()
            for dx, dy in directions:
                nx, ny = cx + dx, cy + dy
                # 检查相邻点是否未访问且高度小于放水点高度
                if l[nx][ny] < h and use[nx][ny] == 0:
                    use[nx][ny] = 1
                    queue.append((nx, ny))
        # 检查司令部是否被淹没
        if use[I][J] == 1:
            print("Yes")
            found = True
    if not found:
        print("No")

dfs实现

python

import sys

sys.setrecursionlimit(300000)
input = sys.stdin.read


# 判断坐标是否有效
def is_valid(x, y, m, n):
    return 0 <= x < m and 0 <= y < n


# 深度优先搜索模拟水流
def dfs(x, y, water_height_value, m, n, h, water_height):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if is_valid(nx, ny, m, n) and h[nx][ny] < water_height_value:
            if water_height[nx][ny] < water_height_value:
                water_height[x][y] = water_height_value
                dfs(nx, ny, water_height_value, m, n, h, water_height)


# 主函数
def main():
    data = input().split()  # 快速读取所有输入数据
    idx = 0
    k = int(data[idx])
    idx += 1
    results = []

    for _ in range(k):
        m, n = map(int, data[idx:idx + 2])
        idx += 2
        h = []
        for i in range(m):
            h.append(list(map(int, data[idx:idx + n])))
            idx += n
        water_height = [[0] * n for _ in range(m)]

        i, j = map(int, data[idx:idx + 2])
        idx += 2
        i, j = i - 1, j - 1

        p = int(data[idx])
        idx += 1

        for _ in range(p):
            x, y = map(int, data[idx:idx + 2])
            idx += 2
            x, y = x - 1, y - 1
            if h[x][y] <= h[i][j]:
                continue

            dfs(x, y, h[x][y], m, n, h, water_height)

        results.append("Yes" if water_height[i][j] > 0 else "No")

    sys.stdout.write("\n".join(results) + "\n")


if __name__ == "__main__":
    main()

dfs的迭代写法

python

import sys

direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]


def dfs(matrix, x, y, target_x, target_y):
    m, n = len(matrix), len(matrix[0])
    h = matrix[x][y]
    stack = [(x, y)]
    visited = [[False for _ in range(n)] for _ in range(m)]

    while stack:
        x, y = stack.pop()
        if x == target_x and y == target_y:
            return True
        visited[x][y] = True
        for dx, dy in direction:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n:  # 确保新坐标在矩阵范围内
                if not visited[nx][ny] and matrix[nx][ny] < h:  # 允许流向等高或更低的位置
                    stack.append((nx, ny))

    return False


# 读取并处理输入
data = sys.stdin.read().split()
k = int(data[0])
id = 1
ans = []

for _ in range(k):
    m, n = int(data[id]), int(data[id + 1])
    id += 2
    matrix = [list(map(int, data[id + i * n:id + (i + 1) * n])) for i in range(m)]
    id += m * n
    a, b = int(data[id]) - 1, int(data[id + 1]) - 1
    id += 2
    p = int(data[id])
    id += 1
    pos = [(int(data[id + i * 2]) - 1, int(data[id + i * 2 + 1]) - 1) for i in range(p)]
    id += p * 2

    result = any(dfs(matrix, x, y, a, b) for x, y in pos)
    ans.append("Yes" if result else "No")

sys.stdout.write("\n".join(ans) + "\n")

python

# 颜鼎堃(24n2400011125)
from sys import stdin
from collections import deque
get = map(int, stdin.read().split())
DIRECTIONS = ((0, 1), (0, -1), (1, 0), (-1, 0))
def bfs(x, y):
    if (x, y) == (I, J):
        return True
    h = mat[x][y]
    queue = deque()
    queue.append((x, y))
    while queue:
        px, py = queue.popleft()
        for dx, dy in DIRECTIONS:
            nx, ny = px + dx, py + dy
            if mat[nx][ny] < h:
                if (nx, ny) == (I, J):
                    return True
                queue.append((nx, ny))
                mat[nx][ny] = h
for _ in range(next(get)):
    yes = False
    M, N = next(get), next(get)
    mat = [[1e9 for i in range(N + 2)]] + [[1e9] + [0 for i in range(N)] + [1e9] for j in range(M)] + [[1e9 for i in range(N + 2)]]
    for i in range(1, 1 + M):
        for j in range(1, 1 + N):
            mat[i][j] = next(get)
    I, J = next(get), next(get)
    for i in range(next(get)):
        if yes:
            next(get)
            next(get)
        else:
            if bfs(next(get), next(get)):
                yes = True
    print("Yes" if yes else "No")

M12029: 水淹七军 ​

标准 AC 解法（推荐） ​

M12029: 水淹七军

标准 AC 解法（推荐）