UVa 10231 Matrix World

题目描述

在现实世界中，有一个 $M\times N$ 的网格地图（$2\le N,M\le 30$）。地图中包含以下几种元素：

• * ：钻石宝藏
• . ：空单元格
• # ：岩石（不可通过）
• X ：警卫机器人
• O ：你的起始位置

你从一个单元格移动到相邻单元格需要 $1$ 秒，收集一个宝藏也需要 $1$ 秒。警卫机器人也以 $1$ 格/秒的速度移动。你不能走出地图边界，警卫也无法进入地图（但警卫可以在地图内移动）。

你需要收集尽可能多的宝藏。如果收集到相同数量的宝藏有多种方案，选择总时间最小的方案。注意：如果你到达一个宝藏单元格的时刻为 $t$，那么你将在 $t+1$ 秒完成收集。如果此时有警卫也到达该单元格（即警卫到达时间 $\le t+1$），则该宝藏不能计入收集结果，因为你没有时间逃脱。

输入包含多个测试用例，输出格式如下：

• 每个用例先输出 Case t:
• 如果无法收集任何宝藏，输出 No treasures can be collected.
• 否则输出：
  • Maximum number of collectible treasures: max.
  • Minimum Time: min sec.
• 每个用例后输出一个空行。

题目分析

本题是一个 带有时间约束的路径规划 + 状态压缩动态规划 问题。地图规模最大为 $30\times 30$，但宝藏数量不超过 $10$，这提示我们可以对宝藏集合进行状态压缩。

核心难点

关键观察

• 玩家的安全条件：若玩家在时刻 $t$ 到达单元格 $(i,j)$，则必须满足 $t<guardTime[i][j]$。对于收集操作，若在时刻 $t$ 开始收集，则收集完成时刻为 $t+1$，必须满足 $t+1<guardTime[i][j]$。
• 警卫的移动不受玩家影响，且所有警卫同时从初始位置出发。这允许我们预先用 $\text{BFS}$ 计算出每个格子的警卫最早到达时间。
• 玩家只能走空单元格、宝藏格、起始格，不能走岩石格。
• 由于地图大小有限，任意两点之间的 安全最短路径 可以预处理（使用 $\text{BFS}$，排除不安全的时刻）。

解题思路

第一步：预处理警卫到达时间

设 $guardTime[x][y]$ 表示任意警卫最早到达单元格 $(x,y)$ 的时间。由于所有警卫同时出发，我们可以将所有警卫的初始位置加入队列，运行多源 $\text{BFS}$。对于岩石格 #，警卫也无法进入，因此 $\text{BFS}$ 中跳过它们。

初始化：每个警卫位置的 $guardTime=0$。
转移：从 $(x,y)$ 走到相邻的 $(nx,ny)$，若 $guardTime[nx][ny]>guardTime[x][y]+1$，则更新并入队。

第二步：计算玩家安全移动的时间矩阵

设起点为 $S$，宝藏共有 $K$ 个（$K\le 10$）。我们构建一个 $(K+1)\times (K+1)$ 的距离矩阵 $dist$，其中索引 $0$ 代表起点，索引 $1\dots K$ 代表各个宝藏。

对于任意两个点 $A$ 和 $B$（可以是起点或宝藏），我们使用 $\text{BFS}$ 计算从 $A$ 到 $B$ 的 安全最短路径长度（即移动步数）。$\text{BFS}$ 的限制条件：

• 只能走 '.'、'*'、'O'（起点位置）。
• 当从当前单元格到达邻居单元格时，设到达邻居的时刻为 $t+1$，必须满足 $t+1<guardTime[neighbor]$。

注意：如果起点本身在时刻 $0$ 就与警卫重合（即起点有警卫），则无法开始任何行动。在我们的多源 $\text{BFS}$ 中，若 $guardTime[S]=0$，则玩家无法存活。

第三步：状态压缩 $\text{DP}$

我们使用二进制掩码表示已经收集的宝藏集合。定义：

$$dp[mask][i]=\text{收集完掩码 }mask\text{ 中的宝藏，且最后收集的宝藏是 }i\text{ 的最小总时间（已完成收集）}$$

其中 $i$ 是宝藏的编号（$0\le i<K$）。注意 $dp[mask][i]$ 已经包含了最后一次收集所需的 $1$ 秒。

初始化：对于每个宝藏 $i$，计算从起点 $S$ 走到宝藏 $i$ 的安全时间 $t_{move}$。若 $t_{move}<\infty$ 且 $t_{move}+1<guardTime[宝{藏}_i]$，则：

$$dp[1\ll i][i]=t_{move}+1$$

状态转移：对于当前状态 $(mask,last)$，尝试前往下一个未收集的宝藏 $nxt$。设从 $last$ 到 $nxt$ 的安全移动时间为 $d=dist[last+1][nxt+1]$（注意索引偏移）。设到达 $nxt$ 的时刻为 $arrive=dp[mask][last]+d$，完成收集的时刻为 $collectEnd=arrive+1$。若 $collectEnd<guardTime[宝{藏}_{nxt}]$，则更新：

$$dp[mask\mid (1\ll nxt)][nxt]=\min (dp[mask\mid (1\ll nxt)][nxt],collectEnd)$$

最终答案：遍历所有 $mask$ 和 $last$，找出 $popcount(mask)$ 最大的 $dp[mask][last]$，若存在多个相同数量的宝藏，取时间最小的。

第四步：边界情况处理

• 如果起点就是宝藏？题目中没有说明，但按逻辑起点是 O，宝藏是 *，二者不同。
• 如果地图中没有宝藏，直接输出无法收集。
• 如果所有宝藏都被警卫包围导致无法安全收集，也输出无法收集。

复杂度分析

• 多源 $\text{BFS}$：$O(M\times N)$
• 预处理每对起点/宝藏之间的安全距离：$O((K+1{)}^2\times M\times N)$，由于 $K\le 10$，$M,N\le 30$，最多约 $11^2\times 900=108900$ 次 $\text{BFS}$，每次 $\text{BFS}$ 为 $O(MN)$，实际可接受。
• DP 状态数：$2^K\times K\approx 1024\times 10=10240$，转移 $O(K)$，总 $O(2^K\times K^2)$，非常快。

代码实现

// Matrix World
// UVa ID: 10231
// Verdict: Accepted
// Submission Date: 2026-05-29
// UVa Run Time: 0.010s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

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

const int INF = 1e9;
const int dx[] = {0, 0, 1, –1};
const int dy[] = {1, –1, 0, 0};

struct State {
int x, y, t;
};

int main() {
int m, n, caseNo = 1;
while (cin >> m >> n) {
vector<string> grid(m);
for (int i = 0; i < m; i++) cin >> grid[i];

vector<pair<int, int>> treasures, guards;
int sx = –1, sy = –1;

// 收集位置信息：'*' 宝藏，'X' 警卫，'O' 起点
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '*') treasures.push_back({i, j});
else if (grid[i][j] == 'X') guards.push_back({i, j});
else if (grid[i][j] == 'O') sx = i, sy = j;
}
}

int tCnt = treasures.size();

// 多源BFS计算警卫到达每个格子的最短时间
vector<vector<int>> guardTime(m, vector<int>(n, INF));
queue<State> q;
for (auto& g : guards) {
guardTime[g.first][g.second] = 0;
q.push({g.first, g.second, 0});
}
while (!q.empty()) {
State cur = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
int nx = cur.x + dx[d], ny = cur.y + dy[d];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
if (grid[nx][ny] == '#') continue;
if (guardTime[nx][ny] > cur.t + 1) {
guardTime[nx][ny] = cur.t + 1;
q.push({nx, ny, cur.t + 1});
}
}
}

// BFS计算从(sx,sy)到(tx,ty)的安全最短路径时间（移动时间）
auto bfs = [&](int sx, int sy, int tx, int ty) -> int {
if (sx == tx && sy == ty) return 0;
vector<vector<int>> dist(m, vector<int>(n, INF));
queue<State> qq;
// 起点必须在警卫到达之前才能开始（严格小于）
if (guardTime[sx][sy] > 0) {
dist[sx][sy] = 0;
qq.push({sx, sy, 0});
}
while (!qq.empty()) {
State cur = qq.front(); qq.pop();
for (int d = 0; d < 4; d++) {
int nx = cur.x + dx[d], ny = cur.y + dy[d];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
if (grid[nx][ny] == '#') continue;
int nt = cur.t + 1;
if (nt >= guardTime[nx][ny]) continue;
if (dist[nx][ny] > nt) {
dist[nx][ny] = nt;
qq.push({nx, ny, nt});
}
}
}
return dist[tx][ty];
};

// 建立距离矩阵：索引0是起点，1..tCnt是宝藏
vector<vector<int>> dist(tCnt + 1, vector<int>(tCnt + 1, INF));
vector<pair<int, int>> points;
points.push_back({sx, sy});
for (auto& t : treasures) points.push_back(t);

for (int i = 0; i <= tCnt; i++) {
for (int j = i + 1; j <= tCnt; j++) {
int d1 = bfs(points[i].first, points[i].second, points[j].first, points[j].second);
int d2 = bfs(points[j].first, points[j].second, points[i].first, points[i].second);
if (d1 < INF) dist[i][j] = d1;
if (d2 < INF) dist[j][i] = d2;
}
}

// 状态压缩DP：dp[mask][last] = 收集完last后总时间（已包含收集的1秒）
vector<vector<int>> dp(1 << tCnt, vector<int>(tCnt, INF));
for (int i = 0; i < tCnt; i++) {
int d = bfs(sx, sy, points[i + 1].first, points[i + 1].second);
if (d < INF) {
int collectEnd = d + 1;
if (collectEnd < guardTime[points[i + 1].first][points[i + 1].second])
dp[1 << i][i] = collectEnd;
}
}

for (int mask = 1; mask < (1 << tCnt); mask++) {
for (int last = 0; last < tCnt; last++) {
if (!(mask >> last & 1)) continue;
if (dp[mask][last] == INF) continue;
for (int nxt = 0; nxt < tCnt; nxt++) {
if (mask >> nxt & 1) continue;
int d = dist[last + 1][nxt + 1];
if (d >= INF) continue;
int arrive = dp[mask][last] + d;
int collectEnd = arrive + 1;
if (collectEnd < guardTime[points[nxt + 1].first][points[nxt + 1].second])
dp[mask | (1 << nxt)][nxt] = min(dp[mask | (1 << nxt)][nxt], collectEnd);
}
}
}

// 找出最大可收集宝藏数及最小时间
int maxTreasures = 0, minTime = INF;
for (int mask = 1; mask < (1 << tCnt); mask++) {
int cnt = __builtin_popcount(mask);
if (cnt < maxTreasures) continue;
for (int last = 0; last < tCnt; last++) {
if (dp[mask][last] < INF) {
if (cnt > maxTreasures) {
maxTreasures = cnt;
minTime = dp[mask][last];
} else if (cnt == maxTreasures) {
minTime = min(minTime, dp[mask][last]);
}
}
}
}

cout << "Case " << caseNo++ << ":\\n";
if (maxTreasures == 0) {
cout << "No treasures can be collected.\\n";
} else {
cout << "Maximum number of collectible treasures: " << maxTreasures << ".\\n";
cout << "Minimum Time: " << minTime << " sec.\\n";
}
cout << "\\n";
}
return 0;
}

总结

本题的核心在于 将警卫的威胁转化为时间约束，然后通过预处理安全路径和状态压缩 $\text{DP}$ 来求解最优收集顺序。这种“时间约束 + 状态压缩”的模型在类似题目（如“收集物品并躲避敌人”）中非常常见，值得熟练掌握。