题目描述

在现实世界中，有一个 $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$，这提示我们可以对宝藏集合进行状态压缩。

核心难点

1. 警卫的动态影响：警卫从各自的位置同时出发，其可达范围随时间扩张。我们需要知道每个单元格被警卫最早到达的时间，从而判断玩家能否安全经过或停留。
2. 收集时间与逃脱时间：玩家在宝藏格必须额外停留 $1$ 秒来完成收集，这比普通移动更危险，因为警卫可能在这 $1$ 秒内赶到。
3. 最优顺序：由于宝藏数量少，我们可以枚举收集顺序，但直接枚举 $10!$ 不可行，因此采用状态压缩 $\text{DP}$。

关键观察

• 玩家的安全条件：若玩家在时刻 $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}$ 来求解最优收集顺序。这种“时间约束 + 状态压缩”的模型在类似题目（如“收集物品并躲避敌人”）中非常常见，值得熟练掌握。