自动搬运

查看原文

来自洛谷，原作者为

	Sol1 博客：sol1.netlify.app

搬运于2025-08-24 22:36:33，当前版本为作者最后更新于2023-05-31 21:30:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

整体想法其实很直接：

• 玩家记录下来自己已经看到的所有位置的信息，然后尝试利用这些信息来推断出自己在地图的哪些位置。
• 假设玩家可以推断出自己的起点是所有起点的一个子集 $S$ 里面的某一个。
• 玩家为了尝试获得更多信息来具体推断自己的起点在 $S$ 里面的哪一个位置，需要向外找安全的位置扩展。具体来说，需要找到一个格子满足：
  • 它与玩家已经走到过的格子相邻；
  • 假设这个格子与起点的相对位置是 $(x,y)$。玩家为了保证自己不被炸到，需要保证对于 $S$ 里面的任意一个起点，均满足与该起点的相对位置是 $(x,y)$ 的格子是安全的。后续我们称这样的格子对于 $S$ 绝对安全。
• 当玩家无法找到这样的格子时，游戏结束，玩家获得自己能走到的范围内的所有金币。
• 答案即为所有游戏结束的情况中，玩家获得金币数的最小值。

当然如果直接实现上述过程肯定写起来非常阴间，而且复杂度不一定对。

因此我们简化一下这个过程。注意到 $S$ 一旦变化为 $S'$，则新的 $S'$ 一定包含于 $S$。因此对于 $S$ 绝对安全的格子对于 $S'$ 也一定绝对安全。所以可以让玩家在此时直接丢弃所有信息重新开始扩展，也可以求得答案。

从而我们实现如下过程：

• 假设目前起点集合是 $S$。
• 从起点开始 BFS 扩展，需要满足扩展到的点对于 $S$ 绝对安全。
• 当无法扩展时，枚举已经看到的所有的点（即扩展到的点和它的外面一圈）。
• 如果某一个位置（设其相对起点的位置是 $(x,y)$）满足：存在 $s_1,s_2\in S$，使得相对 $s_1$ 的位置是 $(x,y)$ 的位置 $p_1$ 和相对 $s_2$ 的位置是 $(x,y)$ 的位置 $p_2$ 在玩家看起来不相同，则可以依照这个点的视野差异分裂 $S$ 并递归进行该过程，并返回递归的两个分叉的返回值的最小值。
• 如果无法分裂 $S$，统计扩展到多少个金币，返回该值。

最终结果就是对所有起点构成的集合进行上述过程的返回值。

直接实现，复杂度 $O(nmS^2)$：每次 BFS 扩展复杂度 $O(nmS)$，同时集合分裂 $S$ 次。

这个复杂度无法通过本题。考虑到瓶颈有两个，分别是：

1. BFS 扩展时判断一个点是否绝对安全，这可以压位：对于每一个 $(x,y)$ 保存一个 64 位整数，第 $i$ 位存储相对第 $i$ 个起点的位置是 $(x,y)$ 的位置是否安全（“安全”指不是 X 和 #），然后就可以用一次位运算判断。
2. 判断一个点是否可以分裂 $S$。这同样可以压位：一个点有三种视觉效果（障碍、空地、金币），对于每一个 $(x,y)$ 保存三个 64 位整数，第 $i$ 位存储相对第 $i$ 个起点的位置是 $(x,y)$ 的位置的视觉效果是不是障碍（空地、金币），然后就可以用三次位运算判断。

进行如上优化后，一轮过程的复杂度下降至 $O(nm)$，总复杂度即下降至 $O(nmS)$ 即可通过。

const int Next[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
const int Sight[9][2] = {{0, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
char mp[405][405], rel[60][815][815];
int n, m, x[60], y[60], s;
long long saf[815][815], sig[815][815][3];
bool vis[815][815], isg[815][815];

inline void Read() {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> mp[i][j];
            if (mp[i][j] == 'S') {
                x[s] = i; y[s] = j;
                s++;
            }
        }
    }
}

inline void Prefix() {
    for (int k = 0;k < s;k++) {
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= m;j++) rel[k][i - x[k] + 402][j - y[k] + 402] = mp[i][j];
        }
    }
    for (int k = 0;k < s;k++) {
        for (int i = 1;i <= 810;i++) {
            for (int j = 1;j <= 810;j++) {
                if (rel[k][i][j] == 'X' || rel[k][i][j] == '#') saf[i][j] |= (1ll << k);
                if (rel[k][i][j] == 'X' || rel[k][i][j] == '.' || rel[k][i][j] == 'S') sig[i][j][0] |= (1ll << k);
                if (rel[k][i][j] == '#') sig[i][j][1] |= (1ll << k);
                if (rel[k][i][j] == 'o') sig[i][j][2] |= (1ll << k);
            }
        }
    }
}

inline int Work(long long sta) {
    //cout << "work " << sta << endl;
    memset(vis, 0, sizeof(vis));
    memset(isg, 0, sizeof(isg));
    queue <pair <int, int> > que;
    que.push(make_pair(402, 402));
    vis[402][402] = 1;
    while (!que.empty()) {
        int x = que.front().first, y = que.front().second;
        que.pop();
        for (int k = 0;k < 4;k++) {
            int tx = x + Next[k][0], ty = y + Next[k][1];
            if (tx < 1 || tx > 810 || ty < 1 || ty > 810) continue;
            if (sta & saf[tx][ty]) continue;
            if (vis[tx][ty]) continue;
            vis[tx][ty] = 1;
            que.push(make_pair(tx, ty));
        }
    }
    for (int i = 1;i <= 810;i++) {
        for (int j = 1;j <= 810;j++) {
            if (vis[i][j]) {
                for (int k = 0;k < 9;k++) {
                    int tx = i + Sight[k][0], ty = j + Sight[k][1];
                    if (tx < 1 || tx > 810 || ty < 1 || ty > 810) continue;
                    isg[tx][ty] = 1;
                }
            }
        }
    }
    for (int i = 1;i <= 810;i++) {
        for (int j = 1;j <= 810;j++) {
            if (isg[i][j]) {
                //cout << i << " " << j << endl;
                for (int c = 0;c < 3;c++) {
                    if ((sig[i][j][c] & sta) != 0 && (sig[i][j][c] & sta) != sta) {
                        return min(Work((sig[i][j][c] & sta)), Work(sta ^ (sig[i][j][c] & sta)));
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1;i <= 810;i++) {
        for (int j = 1;j <= 810;j++) {
            if (vis[i][j] && (sig[i][j][2] & sta) == sta) ans++;
        }
    }
    return ans;
}

int main() {
    Read();
    Prefix();
    //cout << "pass" << endl;
    cout << Work((1ll << s) - 1) << endl;
    return 0;
}