题解 P8169 [eJOI2021] Dungeons

Sol1 · 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;
}