形式化题目

给定 $N$ 行 $M$ 列的网格，* 是泥泞格、. 是干净格。用若干宽度为 $1$、长度任意的 木板盖住所有泥格：每块木板必须沿行方向或列方向、覆盖一串完整的连续格子， 不能压到任何干净格，木板之间可以重叠。求最少需要多少块木板。

把网格做两次切分：

• 横向极大泥段：同一行里一段连续的 *，左右两侧顶住边界或 .；
• 纵向极大泥段：同一列里一段连续的 *，上下两侧顶住边界或 .。

样例 $4\times4$ 的切分结果（行、列从 $0$ 开始编号）：

行段 $5$ 个、列段 $5$ 个。每个泥格 $(r,c)$ 恰好属于一个横向段和一个纵向段。 要证的是：最少木板数等于这个「段-交叉」二分图的最大匹配，其中横向段构成左部、 纵向段构成右部、每个泥格在它的两段之间连一条边。

正解

思路

第一步：朴素做法卡在哪里。

直接搜索「每一块木板从哪开始、往哪个方向摆」是指数级的；换成枚举「哪些段放板」 也有 $2^{\text{行段}+\text{列段}}$ 种——$50\times50$ 全泥时行段列段各 $50$ 个， 约 $2^{100}$，完全不可行。朴素做法的通病是把决策单位放在了「格子/木板」上， 而真正的结构藏在段与段的交叉里。

第二步：每个泥格都是一次「横板还是纵板」的二选一。

一个泥格 $(r,c)$ 想被盖住，只有两条路：要么放一块横向木板盖住它所在的横向段 （以该段的最长形态），要么放一块纵向木板盖住它所在的纵向段。板可以重叠， 所以「横竖都放」也合法，两种选择互不排斥。

把横向段、纵向段看成顶点，泥格 $(r,c)$ 在它的横段与纵段之间连一条边—— 于是「放一块横板」$=$ 选一个左部顶点，「放一块纵板」$=$ 选一个右部顶点， 而「盖住每个泥格」$=$ 每条边至少有一个端点被选中（边的两端都不选， 就等价于这个泥格既没有横板也没有纵板管）。

这正是最小点覆盖（minimum vertex cover）的定义。所以

$G$ 是行段-列段二分图，$\tau$ 是最小点覆盖的大小。注意一个细节： 一个泥格可能同时被横板和纵板盖住（重叠允许），点覆盖同样允许一条边的 两端都被选中——约束只是「至少一端」，二者完全吻合。

样例的二分图长这样（左部横向段、右部纵向段）：

graph LR
  subgraph L["左部：横向段"]
    R0["R0"]
    R1["R1"]
    R2["R2"]
    R3["R3"]
    R4["R4"]
  end
  subgraph R["右部：纵向段"]
    V0["V0"]
    V1["V1"]
    V2["V2"]
    V3["V3"]
    V4["V4"]
  end
  V0 --- R0
  V1 --- R3
  V2 --- R2
  V2 --- R3
  V3 --- R1
  V3 --- R2
  V3 --- R3
  V3 --- R4
  V4 --- R2

样例共 $9$ 个泥格（即 $9$ 条边）。答案 $4$ 对应的木板方案是 $\{$R0, R2, R3, V3$}：横板 $(0,0)、 横板 $(1,1)\!\sim\!(1,3)$、横板 $(2,0)\!\sim\!(2,2)$、纵板 $(0,2)\!\sim\!(3,2)$。 逐格检查：$(0,0)$ 由 R0、$(0,2)$ 由 V3、$(1,1)(1,2)(1,3)$ 由 R2、 $(2,0)(2,1)(2,2)$ 由 R3、$(3,2)$ 由 V3，$9$ 个泥格全部盖住，恰好 $4$ 块。 在图上这 $4$ 个顶点确实覆盖了全部 $9$ 条边。

第三步：König 定理把点覆盖换成匹配。

最小点覆盖在一般图上是 NP-hard 的，但二分图有 König 定理： 最小点覆盖的大小 $=$ 最大匹配的大小，$\tau(G)=\nu(G)$。

一半是显然的：匹配的 $\nu$ 条边端点互不相同，覆盖这些边至少要 $\nu$ 个点， 故 $\tau\ge\nu$。另一半 $\tau\le\nu$ 由构造性证明给出——从每个未匹配的左部点出发 走「未匹配边、匹配边」交替的路，把交替路上「左部未匹配点、右部匹配点」这类 特定端点取出来，恰好拼出 $\nu$ 个点的点覆盖。于是

要提醒的是：数量相等，对象不等。一组最大匹配的边本身不一定是点覆盖 （样例的最大匹配 $\{V0\!-\!R0,\ V1\!-\!R3,\ V2\!-\!R2,\ V3\!-\!R1\}$ 只盖住 $9$ 条边里的 $4$ 条， 漏了 $V4\!-\!R2$ 等其余边），但 König 定理保证「最小点覆盖里有多少个点」这件事可以直接用 「最大匹配有多少条边」算出来，而我们只需要这个数。所以代码里只求匹配数， 不构造具体的木板方案。

样例上验证：最大匹配是 $4$——$V0\!-\!R0$、$V1\!-\!R3$、$V2\!-\!R2$、$V3\!-\!R1$， 只剩 $V4$ 想配 $R2$，而 $R2$ 已被 $V2$ 占用；$V2$ 换到 $V3$ 试过的其他邻居 也腾不出（$V3$ 的邻居 $R1,R3,R4$ 里 $R3$ 被 $V1$ 占且 $V1$ 无处可去）， 增广失败，$\nu=4$，与样例答案 $4$ 一致。

第四步：匈牙利算法求最大匹配。

从右部（纵向段）逐点找增广路：沿未匹配边摸到一个横向段；若它还空着，直接配上； 若已被某个纵向段占用，就顺着那条匹配边下潜到那个纵向段，替它另找新横段…… 这样走出一条「未匹配边、匹配边」交替的路，撞到空闲横段时把整条路翻转， 匹配数加一。seen 集合保证每轮里每个横段只被访问一次。若某个纵向段找不到 增广路，由 Berge 定理，当前匹配已是最大，直接跳过即可。

实现细节。

• 按行读整段字符串；行段编号扫描时用 seg 记录「正在走的段」， 遇 . 归 $-1$、遇 * 且无段时开新段；
• 列段不需要编号表（它只当匹配的发起方），扫到段首时把整段压住的行段号 收进邻接表即可；
• match 挂在横段上：被抢的是横段，下潜一步从横段直接跳到占用它的纵段；
• 增广用显式栈（帧 $=$ 纵向段、下一个待试邻居、最近想抢的横段）， 避免深递归触发 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
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
104
105
106/**
 * 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-10 13:00
 * update_at: 2026-10-10 13:00
 */

// 木板：横木板与竖木板建二分图，König 定理下最小点覆盖 = 最大匹配
#include <cstdio>
#include <vector>
using namespace std;

struct Frame { // 匈牙利算法的显式栈帧
    int v; // 当前纵向木板
    int i; // 下一个待试邻居下标
    int x; // 最近想抢的横向木板
};

int main() {
    int n, m;
    if (scanf("%d %d", &n, &m) != 2) {
        return 0;
    }
    vector<vector<char> > grid(n, vector<char>(m + 1));
    for (int i = 0; i < n; i++) {
        scanf("%s", &grid[i][0]);
    }

    // 横向切分：每格所属横向木板编号（干净格为 -1）
    vector<vector<int> > rows(n, vector<int>(m, -1));
    int row_cnt = 0;
    for (int i = 0; i < n; i++) {
        int seg = -1;
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '.') {
                seg = -1;
            } else {
                if (seg < 0) {
                    seg = row_cnt++;
                }
            }
            rows[i][j] = seg;
        }
    }

    // 纵向木板 → 它压住的横向木板编号列表
    vector<vector<int> > groups;
    for (int c = 0; c < m; c++) {
        int r = 0;
        while (r < n) {
            if (grid[r][c] == '.') {
                r++;
                continue;
            }
            int start = r;
            while (r < n && grid[r][c] == '*') {
                r++;
            }
            vector<int> cur;
            for (int i = start; i < r; i++) {
                cur.push_back(rows[i][c]);
            }
            groups.push_back(cur);
        }
    }

    // 匈牙利：每个纵向段沿「横向段已配的纵向段」下潜找增广路
    vector<int> match(row_cnt, -1);
    vector<char> seen(row_cnt, 0);
    int total = 0;
    for (int v0 = 0; v0 < (int)groups.size(); v0++) {
        for (int i = 0; i < row_cnt; i++) {
            seen[i] = 0;
        }
        vector<Frame> stk;
        Frame first = {v0, 0, -1};
        stk.push_back(first);
        while (!stk.empty()) {
            Frame& fr = stk.back();
            if (fr.i == (int)groups[fr.v].size()) { // 所有出路都试过了，回溯
                stk.pop_back();
                continue;
            }
            int x = groups[fr.v][fr.i];
            fr.i++;
            fr.x = x;
            if (seen[x]) {
                continue;
            }
            seen[x] = 1;
            if (match[x] < 0) { // 撞上空闲横向木板：交替路上每个纵向段各拿一段
                for (int t = (int)stk.size() - 1; t >= 0; t--) {
                    match[stk[t].x] = stk[t].v;
                }
                total++;
                stk.clear();
                break;
            }
            Frame nf = {match[x], 0, x};
            stk.push_back(nf);
        }
    }
    printf("%d\n", total);
    return 0;
}

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#!/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-10-02 02:00
# update_at: 2026-10-02 02:00

import sys


def row_ids(grid: list[str]) -> tuple[list[list[int]], int]:
    """横向切分：每格所属横向木板编号（干净格为 -1），返回编号表与横向木板总数。"""
    table: list[list[int]] = []
    total = 0
    for row in grid:
        ids: list[int] = []
        seg = -1                    # 正在走的横向段编号，-1 表示还没进入任何段
        for ch in row:
            if ch == '.':
                seg = -1
            elif seg < 0:
                seg = total         # 一块新的横向木板从这里开始
                total += 1
            ids.append(seg)
        table.append(ids)
    return table, total


def column_groups(grid: list[str], rows: list[list[int]]) -> list[list[int]]:
    """纵向木板 → 它压住的横向木板编号列表：每列扫到纵向段首时登记整段。"""
    n, m, groups = len(grid), len(grid[0]), []
    for c in range(m):
        r = 0
        while r < n:
            if grid[r][c] == '.':
                r += 1
                continue
            start = r
            while r < n and grid[r][c] == '*':
                r += 1
            groups.append([rows[i][c] for i in range(start, r)])
    return groups


def min_boards(groups: list[list[int]], row_cnt: int) -> int:
    """匈牙利算法：每个纵向段沿「横向段已配的纵向段」下潜找增广路，返回最大匹配。"""
    match = [-1] * row_cnt   # 横向木板 -> 配到的纵向木板，-1 表示还空着
    total = 0
    for v0 in range(len(groups)):
        seen: set[int] = set()
        # 显式栈代替递归：帧 = [纵向木板, 下一个待试邻居下标, 最近想抢的横向木板]
        stack = [[v0, 0, -1]]
        while stack:
            frame = stack[-1]
            u, i = frame[0], frame[1]
            if i == len(groups[u]):  # 这个纵向木板的所有出路都试过了，回溯
                stack.pop()
                continue
            x = groups[u][i]
            frame[1], frame[2] = i + 1, x
            if x in seen:            # 本轮已访问过的横向木板，再走一次没有新信息
                continue
            seen.add(x)
            if match[x] < 0:         # 撞上空闲横向木板：整条交替路上每个纵向段各拿一段
                for f in reversed(stack):
                    match[f[2]] = f[0]
                total += 1
                break
            stack.append([match[x], 0, x])  # 该横向木板已被占用，顺着它的匹配边走到 match[x]
    return total


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    m = int(next(data))
    grid = [next(data).decode() for _ in range(n)]
    rows, row_cnt = row_ids(grid)          # 左部顶点：横向木板
    groups = column_groups(grid, rows)     # 右部顶点：纵向木板，邻接 = 压住的横向木板
    # König 定理：二分图最小点覆盖 = 最大匹配，点覆盖里的每个「段」就是一块木板
    print(min_boards(groups, row_cnt))


if __name__ == "__main__":
    solve()

复杂度

• 建图：行段扫描 $O(NM)$，列段扫描并登记邻接 $O(NM)$（每个泥格登记一条边）。
• 匈牙利：右部每个纵段做一轮增广 DFS，seen 保证一轮内每个横段至多被访问一次， 一轮 $O(|E|)$，总复杂度 $O(|R|\cdot|E|)$。行段、列段各 $\le 2500$、 边数 $\le 2500$，上界 $O(N^2M^2)$；真实数据（10 组、约一半泥格）单组实测约 $0.02$s，远低于限制。
• 空间：row_ids、groups、match、seen 均为 $O(NM)$。

总结

• 关键建模：横向/纵向极大泥段作二分图两侧顶点，每个泥格在两段之间连边； 「盖住每个泥格」恰是「每条边至少一端被选」，答案就是最小点覆盖 $\tau$。 允许木板重叠与点覆盖「两端都选也合法」完全吻合。
• 关键定理：二分图上 König 定理 $\tau=\nu$，答案直接就是最大匹配数。 注意「数量相等、对象不等」——匹配的边本身不必是点覆盖，本题只要数。
• 实现要点：列段无需编号表、match 挂在横段上、显式栈增广、 seen 用当轮局部集合。

图示解析

从题面到答案的主线：

1
2
3
4
5
6
7
8
9
10
11
12
13网格中的每个泥格 (r,c)
        │  它同时属于一个横向极大泥段和一个纵向极大泥段
        ▼
行段 R = 左部 ──边=泥格── 右部 = 列段 V     （按构造就是二分图）
        │  盖住泥格 ⟺ 每条边至少一端被选中（板可重叠 ⟺ 两端都选也合法）
        ▼
答案 = 最小点覆盖 τ(G)
        │  König 定理：二分图 τ = ν
        ▼
答案 = 最大匹配 ν(G)
        │  匈牙利：每个纵段找一条增广路，找不到就停
        ▼
输出 ν(G)

样例 $4\times4$ 上两条线并排看一遍：

最大匹配（$4$ 条边）：$V0\!-\!R0$、$V1\!-\!R3$、$V2\!-\!R2$、$V3\!-\!R1$。

读表时注意两点：点覆盖里 $(1,2)(2,2)$ 两个泥格同时被 R2/R3 和 V3 盖住 （木板重叠，点覆盖允许两端都选）；而最大匹配的 $4$ 条边不是上面的覆盖方案 （它漏了 $V4\!-\!R2$ 这条边）——König 定理只保证两者的数量都是 $4$， 这也正是「只求匹配数、不求方案」的原因。