题目理解

这是一个警察抓强盗的博弈问题，在一个无向图上进行。

• 警察和强盗轮流移动（警察先手）。
• 警察可以移动到相邻节点或保持不动。
• 强盗只能移动到相邻节点（不能不动）。
• 目标：警察能否保证在有限步内与强盗在同一节点相遇。

问题转化

这是一个完全信息的博弈，强盗总是采取最优策略。
我们需要判断警察是否有必胜策略，如果有，还要实现这个策略。

核心思路

1. 博弈状态定义

状态可以用 $(C, R)$ 表示，其中：

• $C$：警察所在节点
• $R$：强盗所在节点

警察的目标是让 $C = R$，强盗的目标是永远避免 $C = R$。

2. 必胜状态分析

从终点状态出发进行逆向分析：

• 如果 $C = R$，警察已经获胜（这是警察的胜利状态）。
• 对于状态 $(C, R)$，如果无论强盗怎么走，警察都能在下一步或后续步骤中获胜，则该状态是警察的必胜状态。

3. 状态扩展

考虑状态 $(C, R)$ 是警察必胜的，如果：

1. 警察的回合：存在一个移动（包括不动）使得新状态 $(C', R)$ 是警察必胜的；或者
2. 强盗的回合：对于强盗的所有可能移动 $R \to R'$，状态 $(C, R')$ 都是警察必胜的。

算法实现

代码使用了多源 BFS + 度数计数的方法来标记必胜状态。

数据结构

• w[u][v]：标记状态 $(u, v)$ 是否是警察必胜
• l[u][v]：记录在状态 $(u, v)$ 时，警察应该移动到的节点
• c[u][v]：计数在状态 $(u, v)$ 时，有多少强盗的移动会导致警察必胜
• d[i]：节点 $i$ 的度数

算法步骤

1. 初始化：所有 $C = R$ 的状态是必胜的，加入队列
2. BFS 扩展：
   • 从队列中取出状态 $(u, v)$
   • 考虑强盗的上一步：如果强盗从 $v'$ 走到 $v$，且所有强盗从 $v'$ 的移动都导致警察必胜，则 $(u, v')$ 也是必胜的
   • 考虑警察的上一步：如果警察能从 $u'$ 走到 $u$，且存在移动使警察到达必胜状态，则 $(u', v)$ 也是必胜的
3. 寻找起始位置：找到某个 $p$ 使得对所有 $r$，$(p, r)$ 都是必胜的

代码解析

int start(int n, bool a[500][500]) {
    queue<pair<int, int>> q;
    vector w(n, vector<bool>(n));  // 必胜标记
    vector<int> d(n);              // 节点度数
    vector c(n, vector<int>(n));   // 必胜计数
    l = c;                         // 移动策略

    // 初始化：相同位置是必胜状态
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (a[i][j])
                d[i]++, w[i][j] = 1, l[i][j] = j, q.emplace(i, j);
    
    // BFS 扩展必胜状态
    while (!q.empty()) {
        auto [u, v] = q.front();
        q.pop();

        // 考虑强盗的上一步
        for (int i = 0; i < n; i++)
            if (a[v][i] && ++c[u][i] == d[i]) {
                if (!w[u][i])
                    w[u][i] = 1, l[u][i] = u, q.emplace(u, i);
                
                // 考虑警察的上一步  
                for (int j = 0; j < n; j++)
                    if (a[u][j] && !w[j][i])
                        w[j][i] = 1, l[j][i] = u, q.emplace(j, i);
            }
    }

    // 寻找必胜起始位置
    for (int i = 0; i < n; i++)
        if (*min_element(w[i].begin(), w[i].end()))
            return p = i;

    return -1;
}

int nextMove(int r) {
    return p = l[p][r];  // 根据预计算的策略移动
}

关键技巧

1. 逆向 BFS：从结束状态（相遇）向前推导必胜状态
2. 度数计数：只有当强盗的所有移动都导致警察必胜时，该状态才是警察必胜的
3. 策略预计算：在 start 中预先计算所有状态的移动策略，nextMove 只需查表

复杂度分析

• 时间复杂度：$O(N^3)$，每个状态 $(u, v)$ 需要检查所有相邻节点
• 空间复杂度：$O(N^2)$，存储所有状态的标记和策略

算法标签

• 博弈论
• 图论
• 广度优先搜索
• 必胜状态分析

总结

本题通过逆向状态扩展和度数计数的方法，高效地解决了警察与强盗的博弈问题。
核心思想是从结束状态出发，逐步标记所有警察必胜的状态，并记录最优移动策略。
这种方法确保了警察在面对最优策略的强盗时，仍然能够保证获胜。