車的放置

形式化题目

给定 $N \times M$ 的棋盘，其中有 $T$ 个格子被禁止放置。要在未被禁止的格子上放尽可能多的車，使得任意两个車不在同一行、也不在同一列（車攻击整行整列，但不会被空格或禁格阻挡）。求最多能放的車数。

输入样例： $N=M=8$ ，无禁格时，答案为 $8$ 。

正解

思路

朴素做法：枚举每个格子放/不放，检查两两是否冲突。指数级复杂度， $N,M \le 200$ 时完全不可行，也看不出任何结构。

关键转化：两个車冲突当且仅当它们同行或同列。把"行"和"列"看成两类对象：

二分图左侧节点 = 第 $1 \sim N$ 行；
二分图右侧节点 = 第 $1 \sim M$ 列；
每个可放的格子 $(i,j)$ 是一条左 $i$ — 右 $j$ 的边。

放一个車在 $(i,j)$ ，相当于选定这条边；"任意两个車不同行不同列"恰好意味着每个行节点、每个列节点至多被一条选中的边覆盖——这正是匹配的定义。所以答案就是该二分图的最大匹配，禁格只需不建对应的边。

一个容易想错的地方：禁格只表示"这里不能放"，不会挡住車的攻击路线（与"炮"的隔子规则不同），所以不需要按禁格把行/列切段，直接整体建图即可。

graph LR
    subgraph 行节点
        R1["行1"]
        R2["行2"]
        R3["行3"]
    end
    subgraph 列节点
        C1["列1"]
        C2["列2"]
        C3["列3"]
    end
    R1 --- C1
    R1 --- C2
    R2 --- C2
    R2 --- C3
    R3 --- C1
    R3 --- C3
    style R1 --- C1 stroke:#e11d48,stroke-width:4px
    style R2 --- C3 stroke:#e11d48,stroke-width:4px
    style R3 --- C2 stroke:#e11d48,stroke-width:4px

图中展示了 $3\times3$ 无禁格棋盘：红色加粗的三条边 $(1,1),(2,3),(3,2)$ 两两不共端点，是一组大小为 $3$ 的匹配，对应棋盘上三个互不攻击的車——而 $3$ 恰好是 $3\times3$ 棋盘的上限（每行至多一个車）。禁格变多时，删去相应边，最大匹配会随之变小；求最大匹配即可得到答案。

求最大匹配用 Hopcroft–Karp 算法：每轮 BFS 从所有未匹配的左部点分层，找到一条通向未匹配右部点的最短增广路族，再沿分层图 DFS 并行增广。相比逐点增广的匈牙利算法，它把轮数从 $O(V)$ 降到 $O(\sqrt V)$ ，对 $N,M\le 200$ （边数最多 $4\times10^4$ ）非常轻松。

代码

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/**
 * 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
 */

// 車的放置：行与列传匹配，每个非禁格是一条边，最大匹配 = 最多車数
#include <cstdio>
#include <vector>
using namespace std;

const int INF = 1 << 30;

int n, m;
vector<vector<int> > adj;
vector<int> match_l, match_r, dist;

// Hopcroft-Karp 增广（递归深度不超过层数）
bool dfs_augment(int u) {
    for (int i = 0; i < (int)adj[u].size(); i++) {
        int v = adj[u][i];
        int w = match_r[v];
        if (w < 0 || (dist[w] == dist[u] + 1 && dfs_augment(w))) {
            match_l[u] = v;
            match_r[v] = u;
            return true;
        }
    }
    dist[u] = INF; // 本轮失败，剪枝
    return false;
}

int main() {
    int t;
    if (scanf("%d %d %d", &n, &m, &t) != 3) {
        return 0;
    }
    vector<char> ok((long long)n * m, 1);
    for (int i = 0; i < t; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        ok[(long long)(x - 1) * m + (y - 1)] = 0; // 禁格坐标 1-indexed
    }
    adj.assign(n, vector<int>());
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (ok[(long long)i * m + j]) {
                adj[i].push_back(j);
            }
        }
    }

    match_l.assign(n, -1);
    match_r.assign(m, -1);
    dist.assign(n, INF);
    int ans = 0;
    while (true) {
        vector<int> q;
        for (int u = 0; u < n; u++) {
            bool free_l = match_l[u] == -1;
            dist[u] = free_l ? 0 : INF;
            if (free_l) {
                q.push_back(u);
            }
        }
        bool found = false;
        for (int h = 0; h < (int)q.size(); h++) {
            int u = q[h];
            for (int i = 0; i < (int)adj[u].size(); i++) {
                int v = adj[u][i];
                int w = match_r[v];
                if (w == -1) {
                    found = true; // 到达未匹配右点，存在增广路
                } else if (dist[w] == INF) {
                    dist[w] = dist[u] + 1;
                    q.push_back(w);
                }
            }
        }
        if (!found) {
            break;
        }
        for (int u = 0; u < n; u++) {
            if (match_l[u] == -1 && dfs_augment(u)) {
                ans++;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

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
61import sys
from collections import deque


def main() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m, t = next(data), next(data), next(data)
    forb = set()
    for _ in range(t):
        x, y = next(data), next(data)  # 禁格坐标 1-indexed，转 0-indexed
        forb.add((x - 1, y - 1))

    # 車攻击整行整列且不被空格阻挡：第 i 行的车与第 j 列的位置一一对应，
    # 每个非禁格 (i,j) 是一条边，放車两两不共行共列 <=> 二分图最大匹配
    adj: list[list[int]] = [[] for _ in range(n)]
    for x, y in forb:
        pass
    ok: list[list[bool]] = [[True] * m for _ in range(n)]
    for x, y in forb:
        ok[x][y] = False
    for i in range(n):
        adj[i] = [j for j in range(m) if ok[i][j]]

    # Hopcroft-Karp 二分图最大匹配，O(E*sqrt(V))
    matchL = [-1] * n
    matchR = [-1] * m
    ans = 0
    INF = 1 << 30
    sys.setrecursionlimit(1 << 20)
    while True:
        dist = [INF] * n
        q = deque(u for u in range(n) if matchL[u] == -1)  # 未匹配左点分层
        for u in q:
            dist[u] = 0
        found = False
        while q:
            u = q.popleft()
            for v in adj[u]:
                w = matchR[v]
                if w == -1:
                    found = True  # 到达未匹配右点，存在增广路
                elif dist[w] == INF:
                    dist[w] = dist[u] + 1
                    q.append(w)
        if not found:
            break

        def dfs(u: int) -> bool:
            for v in adj[u]:
                w = matchR[v]
                if w == -1 or (dist[w] == dist[u] + 1 and dfs(w)):
                    matchL[u], matchR[v] = v, u
                    return True
            dist[u] = INF  # 本轮失败，剪枝
            return False

        ans += sum(dfs(u) for u in range(n) if matchL[u] == -1)
    print(ans)


main()

复杂度

时间复杂度：Hopcroft–Karp 为 $O(E\sqrt V)$ ，其中 $E \le NM = 4\times 10^4$ ， $V = N+M \le 400$ ，约 $10^6$ 级别；逐点增广的匈牙利算法 $O(VE)$ 也能通过，但 Hopcroft–Karp 常数更稳。
空间复杂度： $O(NM)$ ，存邻接表与匹配数组。

总结

車的攻击只与"行、列"两个维度有关，因此把"每行至多一个、每列至多一个"翻译成图论语言：行、列为二分图两侧，可放格为边，互不攻击的車集合就是一组匹配，答案即最大匹配。禁格只删边、不切段。求解用 Hopcroft–Karp 二分图最大匹配， $O(E\sqrt V)$ 内完成。"棋盘放置冲突 → 二分图匹配"是这类问题的通用套路，同类题还有炮的放置（禁格阻挡攻击时需按禁格切段后建图）、基因相似度匹配等。

图示解析

从棋盘到匹配

以 $3\times3$ 棋盘、禁格 $(2,2)$ 为例，对比"能否互相攻击"与"是否共享行列"：

格子位置	与 $(1,1)$ 的車	是否共享行/列	是否可同时放置
$(1,3)$	同行	是	否
$(3,1)$	同列	是	否
$(2,2)$	不同行不同列	否	否（禁格）
$(2,3)$	不同行不同列	否	是

可见"互不攻击" ⇔ “不共享行列” ⇔ “对应边不共享端点”，最后一条正是二分图匹配的定义。于是整个问题被压缩为一张 $N+M$ 个点、 $NM-T$ 条边的二分图，最大匹配数即答案。 $8\times8$ 无禁格时，最大匹配显然为 $8$ （每行恰好放一个），与样例输出一致。

目录

形式化题目

正解

思路

代码

复杂度

总结

图示解析

从棋盘到匹配