题意简述

有一个 $n \times m$ 的网格，开始时所有格子都是“未重建”状态。

政府可以先手动重建一些格子。之后，如果一个格子满足：

• 它在上下相邻格子中，至少有一个已经重建；
• 它在左右相邻格子中，至少有一个已经重建；

那么这个格子也能被“带动重建”。

要求最少手动重建多少个格子，才能最终让整个矩阵全部重建。

核心观察

我们考虑这样两个集合：

• 当前哪些行里至少有一个已经重建的格子；
• 当前哪些列里至少有一个已经重建的格子。

关键结论是：

无论进行多少次“相邻援助”，这两个集合都不会发生变化。

为什么？

设某个新格子 $(i,j)$ 被重建了，那么根据题意：

• 它所在列 $j$ 中，必须原本就有一个上下相邻的已重建格子；
• 它所在行 $i$ 中，必须原本就有一个左右相邻的已重建格子。

也就是说：

• 第 $i$ 行早就已经出现在“有重建格子”的行集合里；
• 第 $j$ 列早就已经出现在“有重建格子”的列集合里。

所以，新重建一个格子，不会让“出现过重建格子的行或列”新增。

这就是本题最重要的不变量。

下界分析

如果最后整个矩阵都要被重建，那么显然：

• 每一行最后都必须出现重建格子；
• 每一列最后都必须出现重建格子。

而由于上面说的那个不变量，这意味着：

在最开始手动选择的那些格子中，就必须已经覆盖所有行和所有列。

于是答案至少满足：

$$ans \ge \max(n,m)$$

因为：

• 想覆盖全部 $n$ 行，至少要让这 $n$ 行都出现；
• 想覆盖全部 $m$ 列，至少要让这 $m$ 列都出现。

一个格子只能同时属于 $1$ 行和 $1$ 列，所以最少不可能小于 $\max(n,m)$。

构造达到下界

接下来证明这个下界是可以达到的。

不妨设：

$$n \le m$$

那么我们这样构造初始手动重建的格子：

$$(1,1),(2,2),(3,3),\dots,(n,n),(n,n+1),(n,n+2),\dots,(n,m) $$

也就是：

• 先选主对角线上的 $n$ 个格子；
• 再把第 $n$ 行从第 $n+1$ 列到第 $m$ 列全部选上。

总共选了：

$$n + (m-n) = m$$

个格子，也就是：

$$m = \max(n,m)$$

为什么这个构造可行

我们来说明，按上面的方式选点后，整个矩阵最终都能被重建。

对于任意一个格子 $(i,j)$：

当 $j \le n$ 时

• 第 $i$ 行中有格子 $(i,i)$ 已经被手动重建；
• 第 $j$ 列中有格子 $(j,j)$ 已经被手动重建。

所以这个格子所在的行、列都已经“连通到重建区域”，之后可以逐步传播出来。

当 $j > n$ 时

• 第 $i$ 行中依然有 $(i,i)$；
• 第 $j$ 列中有 $(n,j)$，因为第 $n$ 行后半段全被我们选了。

所以这种格子同样也能被逐步带动重建。

因此整个矩阵最终都能被完全重建。

于是：

$$ans \le \max(n,m)$$

结合前面的下界：

$$ans \ge \max(n,m)$$

可得最终答案就是：

$$ans = \max(n,m)$$

结论

每组测试数据直接输出：

$$\max(n,m)$$

代码实现

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    cout << max(n, m) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

复杂度分析

每组测试数据只做一次比较，因此：

$$O(1)$$

总空间复杂度也是：

$$O(1)$$