usaco-4.4.3 重叠的图像

形式化题目

给定一个大小为 $H \times W$ （ $3 \le H, W \le 30$ ）的字符网格，由若干个不同大写字母构成的矩形边框（边宽为 1，长宽均 $\ge 3$ ）自底向上依次覆盖堆叠而成。未被覆盖的背景为 .。每个矩形的每条边至少有一部分在最终网格中可见。求所有可能的从底部到顶部的堆叠顺序（即拓扑序列）。若有多种可能，按字典序升序输出所有情况。

正解

思路

本题由两部分组成：依赖关系的确定（建模建图） 与 全拓扑排序的枚举（搜索输出）。

1. 还原每个矩形边框的几何范围

题目给出了关键条件：每个矩形的每条边中，至少有一部分是可见的。这意味着对于任意出现在网格中的字母 $C$ ：

其最上边缘所在行一定是所有字母 $C$ 出现位置的最小行号 $r_{\min}$ ；
最下边缘所在行一定是最大行号 $r_{\max}$ ；
最左边缘所在列一定是最小列号 $c_{\min}$ ；
最右边缘所在列一定是最大列号 $c_{\max}$ 。

因此，只需遍历一次网格，即可唯一确定每个矩形边框的四条外边构成的空心矩形区域：

上边： $(r_{\min}, c)$ ，其中 $c_{\min} \le c \le c_{\max}$
下边： $(r_{\max}, c)$ ，其中 $c_{\min} \le c \le c_{\max}$
左边： $(r, c_{\min})$ ，其中 $r_{\min} \le r \le r_{\max}$
右边： $(r, c_{\max})$ ，其中 $r_{\min} \le r \le r_{\max}$

2. 由覆盖关系构建有向无环图（DAG）

对于矩形 $u$ ，其原本四条边上应当全部由字母 $u$ 填充。如果最终网格中该边上的某个位置显示的是字母 $v$ （且 $v \ne u$ ），说明矩形 $v$ 覆盖在了矩形 $u$ 之上。因此，在自底向上的堆叠顺序中，矩形 $u$ 必须早于矩形 $v$ 被放置。我们建立一条有向边：

u \to v

表示

u

必须排在

v

前面（

u

在更底层，

v

在更顶层）。

3. 回溯搜索所有合法的全拓扑序列

问题转化为了：在一个有向无环图（DAG）中，求出所有自底向上的拓扑排序，并按字典序输出。由于字母数量最多 26 个，我们可以采用深度优先搜索（DFS）加回溯：

每一层按字典序枚举所有当前入度为 0 且尚未加入序列的字母 $u$ ；
将 $u$ 追加到当前路径，并将其所有后继节点 $v$ 的入度减 1；
递归搜索下一层；
回溯时恢复入度并从路径中弹出 $u$ ；
当序列长度等于总字母数时，找到一种合法的全排列并输出。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47

from collections import defaultdict
import sys


def solve() -> None:
    tokens = sys.stdin.buffer.read().split()
    if not tokens:
        return
    data = iter(tokens)
    h = int(next(data))
    w = int(next(data))
    grid = [next(data).decode() for _ in range(h)]

    # 1. 提取所有出现的矩形字母及其边界 (min_r, max_r, min_c, max_c)
    letters = sorted(set("".join(grid)) - {"."})
    bounds = {
        ch: (
            min(r for r in range(h) for c in range(w) if grid[r][c] == ch),
            max(r for r in range(h) for c in range(w) if grid[r][c] == ch),
            min(c for r in range(h) for c in range(w) if grid[r][c] == ch),
            max(c for r in range(h) for c in range(w) if grid[r][c] == ch),
        )
        for ch in letters
    }

    # 2. 统计每个矩形边框上覆盖它的其它字母：ch 必须在 top 之前放置 (ch -> top)
    # 即 ch 在底层，top 覆盖在 ch 上面
    edges = defaultdict(set)
    in_degree = {ch: 0 for ch in letters}
    for ch, (r1, r2, c1, c2) in bounds.items():
        border_cells = (
            [(r1, c) for c in range(c1, c2 + 1)]
            + [(r2, c) for c in range(c1, c2 + 1)]
            + [(r, c1) for r in range(r1, r2 + 1)]
            + [(r, c2) for r in range(r1, r2 + 1)]
        )
        for r, c in border_cells:
            top = grid[r][c]
            if top != ch and top in bounds and top not in edges[ch]:
                edges[ch].add(top)
                in_degree[top] += 1

    # 3. 回溯搜索所有合法的自底向上拓扑序（按字典序输出）
    n = len(letters)
    path: list[str] = []

    def dfs() -> None:
        if len(path) == n:
            sys.stdout.write("".join(path) + "\n")
            return
        for ch in letters:
            if ch not in path and in_degree[ch] == 0:
                for nxt in edges[ch]:
                    in_degree[nxt] -= 1
                path.append(ch)

                dfs()

                path.pop()
                for nxt in edges[ch]:
                    in_degree[nxt] += 1

    dfs()


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 11:32
 * update_at: 2026-10-06 11:32
 */

// main.cpp：重叠的图像（usaco 4.4.3 frameup）
// 做法：由每个字母出现位置的极值坐标还原矩形边框，
//       边框上出现的其它字母说明后者覆盖在前者之上，连边 u -> v，
//       最后回溯搜索所有合法的自底向上拓扑序，按字典序输出。

#include <cstdio>
#include <cstring>

typedef long long ll;

const int MAXN = 35;

int h, w;
char grid[MAXN][MAXN];      // 输入网格
char path[30];              // 当前正在构造的拓扑序列
bool used[26];              // 某个字母是否已经在当前序列中
bool exist[26];             // 某个字母是否出现
bool adj[26][26];           // adj[u][v] = true 表示 u 必须排在 v 前面（v 覆盖 u）
int indeg[26];              // 拓扑搜索用入度
int minr[26], maxr[26], minc[26], maxc[26]; // 每个字母边框的极值坐标
int total = 0;              // 出现的矩形（字母）个数

// 用边框上的覆盖关系建图：u 的边上出现字母 v（v != u），说明 v 盖住了 u，连边 u -> v
void build_graph() {
    memset(adj, 0, sizeof(adj));
    memset(indeg, 0, sizeof(indeg));
    for (int u = 0; u < 26; ++u) {
        if (!exist[u]) continue;
        for (int c = minc[u]; c <= maxc[u]; ++c) { // 上下两条边
            int v = grid[minr[u]][c] - 'A';
            if (v != u && exist[v] && !adj[u][v]) { adj[u][v] = true; ++indeg[v]; }
            v = grid[maxr[u]][c] - 'A';
            if (v != u && exist[v] && !adj[u][v]) { adj[u][v] = true; ++indeg[v]; }
        }
        for (int r = minr[u]; r <= maxr[u]; ++r) { // 左右两条边
            int v = grid[r][minc[u]] - 'A';
            if (v != u && exist[v] && !adj[u][v]) { adj[u][v] = true; ++indeg[v]; }
            v = grid[r][maxc[u]] - 'A';
            if (v != u && exist[v] && !adj[u][v]) { adj[u][v] = true; ++indeg[v]; }
        }
    }
}

// 回溯搜索所有拓扑序：dep 表示已确定序列的前 dep 个字母
void dfs(int dep) {
    if (dep == total) { // 序列完整，输出一种合法的自底向上顺序
        path[total] = '\0';
        printf("%s\n", path);
        return;
    }
    for (int u = 0; u < 26; ++u) { // 按字母序枚举，保证输出按字典序
        if (!exist[u] || used[u] || indeg[u] != 0) continue;
        used[u] = true;
        path[dep] = 'A' + u;
        for (int v = 0; v < 26; ++v) // 拿掉 u 之后，它的后继入度减一
            if (adj[u][v]) --indeg[v];

        dfs(dep + 1);

        for (int v = 0; v < 26; ++v) // 回溯恢复
            if (adj[u][v]) ++indeg[v];
        used[u] = false;
    }
}

int main() {
    scanf("%d %d", &h, &w);
    for (int r = 0; r < h; ++r) scanf("%s", grid[r]);

    memset(exist, 0, sizeof(exist));
    memset(used, 0, sizeof(used));
    // 1. 扫描网格，求每个字母出现位置的极值行列号
    //    因为每条边至少有一部分可见，极值行列一定是边框四条边所在的位置
    for (int r = 0; r < h; ++r) {
        for (int c = 0; c < w; ++c) {
            if (grid[r][c] == '.') continue;
            int u = grid[r][c] - 'A';
            if (!exist[u]) {
                exist[u] = true;
                minr[u] = maxr[u] = r;
                minc[u] = maxc[u] = c;
                ++total;
            } else {
                if (r < minr[u]) minr[u] = r;
                if (r > maxr[u]) maxr[u] = r;
                if (c < minc[u]) minc[u] = c;
                if (c > maxc[u]) maxc[u] = c;
            }
        }
    }

    build_graph();
    dfs(0);
    return 0;
}

复杂度

时间复杂度：
- 极值坐标提取：扫描网格 $O(H \cdot W)$ ，最多 26 个字母，复杂度为 $O(26 \cdot H \cdot W)$ 。
- 边框覆盖检查建图：对每个矩形扫描四条边周长，最多 $26 \times 2(H + W)$ 步，常数极小。
- 回溯搜索全拓扑排序：状态空间受拓扑偏序严格约束，只有合法的拓扑前缀才会继续展开，耗时主要取决于解的个数 $K$ 。对于全部数据，耗时均在 0.1 秒以内。
空间复杂度：存储邻接表与入度数组需 $O(|V|^2)$ ，递归栈深度最大为 $|V| \le 26$ ，空间复杂度为 $O(H \cdot W + |V|^2)$ ，完全在内存限制之内。

总结

利用“边框每条边至少有一部分可见”的性质，通过坐标极值唯一逆向推导各矩形边框。
通过边框上的字符覆盖重叠关系导出偏序关系，建立有向无环图（DAG）。
利用字典序回溯枚举 DAG 的全拓扑排序，结构清晰、实现紧凑。

图示解析

以样例数据为例，字母间的覆盖依赖关系如下：

graph TD
    E[E] --> D[D]
    D[D] --> A[A]
    D[D] --> B[B]
    B[B] --> C[C]
    A[A] --> B[B]

在网格中，矩形边框上的覆盖产生先后依赖，如：

$E$ 的边框被 $D$ 覆盖，必须先放 $E$ 再放 $D$ ；
$D$ 的边框被 $A$ 和 $B$ 覆盖，必须先放 $D$ 再放 $A, B$ ；
$A$ 的边框被 $B$ 覆盖，必须先放 $A$ 再放 $B$ ；
$B$ 的边框被 $C$ 覆盖，必须先放 $B$ 再放 $C$ 。

最终自底向上的合法堆叠顺序即为拓扑序：EDABC。