UVa 10607 Siege

题目描述

平面国可以表示为一个 $M\times N$ 的矩形网格，每个格子属于一个省。省是四连通（上下左右相邻）的连通块。地图上的每个省用一个 $\text{ASCII}$ 字符标记。

首都标记为字符 A，且首都所在的省不包含地图边界上的任何格子。

邪恶国王想要征服首都。为了包围首都，他必须征服所有与首都相邻的省。两个省相邻当且仅当存在两个格子有一条公共边且分属这两个省。

征服规则如下：

• 边境省（包含地图边界格子的省）可以直接征服。
• 非边境省只能通过与已被征服的省相邻来征服。

重要限制：不存在一个格子与超过 $3$ 个其他省相邻，这意味着首都的四个方向上不可能出现四个不同的省。

国王希望用最少的征服省份数完成对首都的包围。请求出这个最小值，如果不可能完成，输出 $-1$。

输入格式

多组测试数据。每组第一行包含 $M$ 和 $N$（$3<M,N<200$）。接下来 $M$ 行每行 $N$ 个字符表示地图。输入以 $M=0,N=0$ 结束。

输出格式

对于每组数据，输出最少需要征服的省份数，若不可能则输出 $-1$。

样例

输入：

5 6
BBBBBB
BCCCBB
BCAbBZ
BDDDbZ
33333Z
3 3
BBB
BAB
0 0

输出：

4
1

题目分析

问题本质

这是一个在省份级别图上的 可达性与最短路径 问题。我们需要：

关键观察

• 首都 A 不是边境省，但它可能在内部或边界附近。

• 由于“一个格子最多邻接 $3$ 个不同省份”的限制，首都最多被 $3$ 个不同省份包围（东南西北四个方向中至少有一对属于同一省份）。

• 如果首都内部包围着其他省份（即存在某个非 A 省的所有格子都被 A 的格子包围），那么这些省份永远无法被征服，因为：

  • 它们不与边境相连（无法直接征服）。
  • 它们被 A 包围，而 A 未被征服（征服规则不允许先征服 A）。
  • 即使先征服了 A 的邻省，也无法进入 A 内部去征服这些被包围的省。

  因此这种情况应输出 $-1$。

可达性判断

判断某个非 A 省是否被 A 包围的方法：

• 从所有边境省出发，在省份邻接图上进行广度优先搜索（$\text{BFS}$）。
• 关键：不能经过首都 A（遇到 A 时停止扩展）。
• 如果最终所有非 `A$ 省都被访问到，说明它们都能从边境到达，否则存在被包围的省份。

包围首都的最少征服数

定义：

• $S$ = 与首都相邻的省份集合，$m=|S|$。
• 如果 $S$ 中存在边境省，那么直接征服 $S$ 中的所有省即可，答案为 $m$。
• 否则，$S$ 中的所有省都不是边境省，它们需要通过其他省份连通到边境。

此时，我们需要选择一个边境省作为起点，沿着省份邻接图（不能经过首都）走到 $S$ 中的某个省，并沿途征服路径上的所有省。设从某个边境省到 $S$ 中某个省的最短路径长度为 $n$（这里的长度定义为 路径上省份的数量，包括终点但不包括起点边境省）。那么：

• 起点边境省：$1$ 个。
• 路径上的其他省（不含边境省和终点）：$n-2$ 个。
• 终点省：$1$ 个（属于 $S$）。
• $S$ 中的其他 $m-1$ 个省。
  总计：$1+(n-2)+1+(m-1)=m+n-1$。

因此，答案为 $m+n-1$，其中 $n=\underset{t\in S}{\min }dist($任意边境省$,t)$，$dist$ 是省份图上不经过首都的最短路径长度（按省份数量计数，起点边境省距离为 $1$）。

解题步骤

第一步：省份标号

使用 $\text{BFS}$ 或 $\text{DFS}$ 对网格进行四连通区域标记，给每个格子赋予所属省份的编号 $0,1,\dots ,K-1$。记录首都的省份编号 $capId$。

第二步：构建省份邻接图

遍历每个格子，检查其四个邻居，若邻居属于不同省份，则在两个省份之间建立无向边（使用集合去重）。

第三步：判断是否存在被包围的省份

第四步：计算最小征服数

复杂度分析

• 省份标号：$O(M\times N)$。
• 建图：$O(M\times N)$。
• $\text{BFS}$：$O(K+E)$，其中 $K$ 是省份数（$K<100$），$E$ 是省份间边数（最多 $O(K^2)$）。
• 整体复杂度：$O(M\times N+K^2)$，足够快。

代码实现

// Siege
// UVa ID: 10607
// Verdict: Accepted
// Submission Date: 2026-05-27
// UVa Run Time: 0.000s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

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

int M, N;
vector<string> grid;
int provId[205][205];
int provCount;
vector<pair<int,int>> dirs = {{–1, 0}, {1, 0}, {0, –1}, {0, 1}};

// 四连通区域标记，给每个格子分配省份编号
void labelProvinces() {
provCount = 0;
memset(provId, –1, sizeof(provId));
for (int i = 0; i < M; ++i) for (int j = 0; j < N; ++j) {
if (provId[i][j] != –1) continue;
queue<pair<int,int>> q;
q.push({i, j});
provId[i][j] = provCount;
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (auto [dx, dy] : dirs) {
int nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < M && ny >= 0 && ny < N && provId[nx][ny] == –1 && grid[nx][ny] == grid[x][y]) {
provId[nx][ny] = provCount;
q.push({nx, ny});
}
}
}
++provCount;
}
}

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

while (cin >> M >> N, M || N) {
grid.resize(M);
for (int i = 0; i < M; ++i) cin >> grid[i];

labelProvinces();

// 找到首都的省份编号
int capId = –1;
for (int i = 0; i < M; ++i) for (int j = 0; j < N; ++j)
if (grid[i][j] == 'A') capId = provId[i][j];

// 建图：省份邻接表（使用 set 去重）
vector<set<int>> adj(provCount);
for (int i = 0; i < M; ++i) for (int j = 0; j < N; ++j) {
for (auto [dx, dy] : dirs) {
int ni = i + dx, nj = j + dy;
if (ni >= 0 && ni < M && nj >= 0 && nj < N) {
int u = provId[i][j], v = provId[ni][nj];
if (u != v) adj[u].insert(v);
}
}
}

// 标记边境省
vector<bool> isBorder(provCount, false);
for (int i = 0; i < M; ++i) for (int j = 0; j < N; ++j)
if (i == 0 || i == M – 1 || j == 0 || j == N – 1)
isBorder[provId[i][j]] = true;

// BFS 从所有边境省出发（不经过首都），看能否到达所有非 A 省
vector<bool> reachable(provCount, false);
queue<int> q;
for (int i = 0; i < provCount; ++i)
if (isBorder[i] && i != capId) {
reachable[i] = true;
q.push(i);
}
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (v == capId) continue;
if (!reachable[v]) {
reachable[v] = true;
q.push(v);
}
}
}

// 检查是否有非 A 省无法到达
bool ok = true;
for (int i = 0; i < provCount; ++i)
if (i != capId && !reachable[i]) {
ok = false;
break;
}
if (!ok) {
cout << "-1\\n";
continue;
}

// 找出与首都相邻的省份集合 S
set<int> neighborSet;
for (int i = 0; i < M; ++i) for (int j = 0; j < N; ++j) {
if (provId[i][j] != capId) continue;
for (auto [dx, dy] : dirs) {
int ni = i + dx, nj = j + dy;
if (ni >= 0 && ni < M && nj >= 0 && nj < N) {
int nid = provId[ni][nj];
if (nid != capId) neighborSet.insert(nid);
}
}
}

// 如果 S 中有边境省，直接征服 S 即可
bool hasBorderNeighbor = false;
for (int x : neighborSet)
if (isBorder[x]) {
hasBorderNeighbor = true;
break;
}
if (hasBorderNeighbor) {
cout << neighborSet.size() << '\\n';
continue;
}

// 否则 BFS 计算从边境省到 S 的最短距离（路径上的省份数，起点距离为 1）
vector<int> dist(provCount, –1);
queue<int> bq;
for (int i = 0; i < provCount; ++i)
if (isBorder[i] && i != capId) {
dist[i] = 1;
bq.push(i);
}
while (!bq.empty()) {
int u = bq.front(); bq.pop();
for (int v : adj[u]) {
if (v == capId) continue;
if (dist[v] == –1) {
dist[v] = dist[u] + 1;
bq.push(v);
}
}
}

int minDist = 1e9;
for (int x : neighborSet)
if (dist[x] != –1)
minDist = min(minDist, dist[x]);

cout << neighborSet.size() + minDist – 1 << '\\n';
}

return 0;
}

总结

本题的关键在于理解“包围”的含义以及“被首都包围的省份”无法被征服的判定。通过构建省份级别的图并执行 $\text{BFS}$，可以高效地判断可达性并计算最小征服数。题目中“一个格子最多与三个省相邻”的条件隐含了首都最多被三个省包围，但我们的算法并不依赖这一条件（仅用于保证数据合理性）。

该解法的时间复杂度为 $O(M\times N+K^2)$，空间复杂度 $O(M\times N+K^2)$，可以在给定限制内高效运行。