嘘~ 正在从服务器偷取页面 . . .

CF1201E2 Knightmare (hard) 题解

算法 构造 交互题 博弈论
OI
发布日期:   2024-06-19
更新日期:   2024-06-25
文章字数:   2.1k

CF1201E2 Knightmare (hard) 题解

题目链接：Knightmare (hard)

题意：

本题是交互题。

Alice 和 Bob 在 \(n \times m\) 的国际象棋棋盘上下棋，\(n,m\) 都是偶数。

棋盘上有一个黑棋 \(\unicode{x265E}\) 和一个白棋 \(\unicode{x2658}\) ，白棋先手，走法同国际象棋中的骑士（同中国象棋的马）。

现在双方要将棋子跳到目标点。白棋的目标点是 \(\left(\frac{n}{2}, \frac{m}{2}\right)\)，黑棋的目标点是 \(\left(\frac{n}{2} + 1, \frac{m}{2}\right)\)。

游戏胜利的条件如下：

  • 棋子到达了目标点，且当前对方棋子不能攻击到目标点。
  • 吃掉了对方的棋子。

如果 \(350\) 回合后游戏未结束，则视为平局。

请你帮助 Alice 选择黑棋 \(\unicode{x265E}\) 或白棋 \(\unicode{x2658}\) 以赢得这场游戏。可以证明一定 Alice 存在必胜策略。

交互格式：

读入 \(n,m,x_0,y_0,x_1,y_1(6\le n,m\le 1000)\) 表示棋盘大小以及白棋黑棋的初始位置 \((x_0,y_0)\) 和 \((x_1,y_1)\) 。

此时你应该输出一行 \(\tt BLACK\) 或者 \(\tt WHITE\) ，表示初始选择的棋子是黑棋 \(\unicode{x265E}\) 还是白棋 \(\unicode{x2658}\)。

当轮到你走棋时，输出 \(x,y\) ，表示走到 \((x,y)\) 。如果你获得了胜利，请立刻结束程序。

请注意：交互器是有适应能力的。也就是说，它的招数可能会随着你的招数的变化而变化。

思维题 + 大模拟。

众所周知，在国际象棋中，当 \(\unicode{x265E}\) 和 \(\unicode{x2658}\) 所处的格子异色时，\(\unicode{x2658}\) 可以吃 \(\unicode{x265E}\) ；反之 \(\unicode{x265E}\) 可以吃 \(\unicode{x2658}\) 。

不妨考虑异色的情况，也就是 \(\unicode{x2658}\) 可以吃 \(\unicode{x265E}\) 的情况。

  • 如果 \(\unicode{x2658}\) 到终点的距离小于等于 \(\unicode{x265E}\) 到终点的距离，那跑就完事了，反正 \(\unicode{x265E}\) 肯定吃不了它。

    形式化地，这种情况需要满足 \(\mathrm{dis}(S_\unicode{x2658},T_\unicode{x2658}) \le \mathrm{dis}(S_{\unicode{x265E}}, T_{\unicode{x265E}})\) ，\(S,T\) 表示起点和终点的位置。

  • 反之，\(\unicode{x2658}\) 跑是肯定跑不过了，只能考虑去吃 \(\unicode{x265E}\) 。显然，最好的办法就是往 \(\unicode{x265E}\) 的终点 \(T_{\unicode{x265E}}\) 跑。

    这种情况需要满足 \(\mathrm{dis}(S_{\unicode{x2658}}, T_{\unicode{x265E}}) \le \mathrm{dis}(S_{\unicode{x265E}},T_{\unicode{x2658}}) + 1\) ，加 \(1\) 是因为 \(\unicode{x265E}\) 可能到了终点刚好被 \(\unicode{x2658}\) 一步吃掉

    如果 \(\unicode{x2658}\) 到了 \(\unicode{x265E}\) 的终点 \(T_{\unicode{x265E}}\) 还没吃掉它，那 \(\unicode{x2658}\) 和 \(\unicode{x265E}\) 肯定距离不少于 \(2\) ，此时他们同色。

    然而 \(\unicode{x265E}\) 不可能缩短距离去送死，那么距离就变成了不少于 \(3\) 。

    又因为 \(\mathrm{dis}(T_{\unicode{x2658}}, T_{\unicode{x265E}}) = 3\) ，于是 \(\unicode{x2658}\) 在这种情况下，先一口气冲到 \(T_{\unicode{x265E}}\) ，再跳到 \(T_{\unicode{x2658}}\) 就完事了。

  • 什么？上面两个条件都不满足？那还选什么 \(\unicode{x2658}\) ，直接选 \(\unicode{x265E}\) 跑不就完事了。

于是这道题目就变成了一个大模拟。

时间复杂度 \(\mathcal{O}(nm)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define Fi first
#define Se second
#define N ((int)(1234))

const int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dy[] = {1, -1, 2, -2, 2, -2, 1, -1};

int n, m, f1[N][N], f2[N][N]; pii g1[N][N], g2[N][N];
pii get() { int x, y; cin >> x >> y; return {x, y}; }
void put(int x, int y) { cout << x << ' ' << y << endl; }
bool check(int x1, int y1, int x2, int y2) { 
    for(int i = 0; i < 8; i++) { 
        if(x1 + dx[i] == x2 && y1 + dy[i] == y2) return true;
    } return false;
}
bool safe(int x, int y) { return x > 0 && x <= n && y > 0 && y <= m; };
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    static int x1, y1, x2, y2; cin >> n >> m >> x1 >> y1 >> x2 >> y2;
    if(check(x1, y1, x2, y2)) { return cout << "WHITE\n" << x2 << ' ' << y2 << endl, 0; }
    mem(f1, -1); mem(f2, -1); static queue<pii> que; f1[x1][y1] = 0; que.push({x1, y1});
    while(!que.empty())
    {
        auto [x, y] = que.front(); que.pop();
        for(int i = 0; i < 8; i++)
        {
            const int tx = x + dx[i], ty = y + dy[i];
            if(safe(tx, ty) && f1[tx][ty] == -1) {
                f1[tx][ty] = f1[x][y] + 1; g1[tx][ty] = {x, y}; que.push({tx, ty});
            }
        }
    }
    f2[x2][y2] = 0; que.push({x2, y2});
    while(!que.empty())
    {
        auto [x, y] = que.front(); que.pop();
        for(int i = 0; i < 8; i++)
        {
            const int tx = x + dx[i], ty = y + dy[i];
            if(safe(tx, ty) && f2[tx][ty] == -1) {
                f2[tx][ty] = f2[x][y] + 1; g2[tx][ty] = {x, y}; que.push({tx, ty});
            }
        }
    }
    if((x1 + y1 + x2 + y2) & 1)
    {
        if(f1[n / 2][m / 2] <= f2[n / 2 + 1][m / 2])
        {
            cout << "WHITE" << endl;
            vector<pii> v; int x = n / 2, y = m / 2;
            while(x != x1 || y != y1) {
                v.push_back({x, y}); pii p = g1[x][y]; x = p.Fi, y = p.Se;
            }
            reverse(v.begin(), v.end());
            for(auto p : v)
            {
                put(p.Fi, p.Se); if(p.Fi == n / 2 && p.Se == m / 2) return 0;
                pii q = get(); if(check(p.Fi, p.Se, q.Fi, q.Se)) return put(q.Fi, q.Se), 0;
            }
        }else if(f1[n / 2 + 1][m / 2] <= f2[n / 2 + 1][m / 2] + 1)
        {
            cout << "WHITE" << endl;
            vector<pii> v; int x = n / 2 + 1, y = m / 2;
            while(x != x1 || y != y1) {
                v.push_back({x, y}); pii p = g1[x][y]; x = p.Fi, y = p.Se;
            }
            reverse(v.begin(), v.end());
            for(auto p : v)
            {
                put(p.Fi, p.Se); pii q = get();
                if(check(p.Fi, p.Se, q.Fi, q.Se)) return put(q.Fi, q.Se), 0;
            }
            v.clear(); v.push_back({n / 2, m / 2 + 2});
            v.push_back({n / 2 - 2, m / 2 + 1}); v.push_back({n / 2, m / 2});
            for(auto p : v)
            {
                put(p.Fi, p.Se); if(p.Fi == n / 2 && p.Se == m / 2) return 0;
                pii q = get(); if(check(p.Fi, p.Se, q.Fi, q.Se)) return put(q.Fi, q.Se), 0;
            }
        }else
        {
            cout << "BLACK" << endl;
            vector<pii> v; int x = n / 2 + 1, y = m / 2;
            while(x != x2 || y != y2) {
                v.push_back({x, y}); pii p = g2[x][y]; x = p.Fi, y = p.Se;
            }
            reverse(v.begin(), v.end());
            for(auto p : v)
            {
                pii q = get(); if(check(x2, y2, q.Fi, q.Se)) return put(q.Fi, q.Se), 0;
                put(p.Fi, p.Se); x2 = p.Fi, y2 = p.Se; if(p.Fi == n / 2 + 1 && p.Se == m / 2) return 0;
            }
        }
    }else
    {
        if(f2[n / 2 + 1][m / 2] < f1[n / 2][m / 2])
        {
            cout << "BLACK" << endl;
            vector<pii> v; int x = n / 2 + 1, y = m / 2;
            while(x != x2 || y != y2) {
                v.push_back({x, y}); pii p = g2[x][y]; x = p.Fi, y = p.Se;
            }
            reverse(v.begin(), v.end());
            for(auto p : v)
            {
                pii q = get(); if(check(x2, y2, q.Fi, q.Se)) return put(q.Fi, q.Se), 0;
                put(p.Fi, p.Se); x2 = p.Fi, y2 = p.Se; if(p.Fi == n / 2 + 1 && p.Se == m / 2) return 0;
            }
        }else if(f2[n / 2][m / 2] <= f1[n / 2][m / 2])
        {
            cout << "BLACK" << endl;
            vector<pii> v; int x = n / 2, y = m / 2;
            while(x != x2 || y != y2) {
                v.push_back({x, y}); pii p = g2[x][y]; x = p.Fi, y = p.Se;
            }
            reverse(v.begin(), v.end());
            for(auto p : v)
            {
                pii q = get(); if(check(x2, y2, q.Fi, q.Se)) return put(q.Fi, q.Se), 0;
                put(p.Fi, p.Se); x2 = p.Fi, y2 = p.Se; if(p.Fi == n / 2 + 1 && p.Se == m / 2) return 0;
            }
            v.clear(); v.push_back({n / 2 + 1, m / 2 + 2});
            v.push_back({n / 2 + 3, m / 2 + 1}); v.push_back({n / 2 + 1, m / 2});
            for(auto p : v)
            {
                pii q = get(); if(check(x2, y2, q.Fi, q.Se)) return put(q.Fi, q.Se), 0;
                put(p.Fi, p.Se); x2 = p.Fi, y2 = p.Se;
            }
        }else
        {
            cout << "WHITE" << endl;
            vector<pii> v; int x = n / 2, y = m / 2;
            while(x != x1 || y != y1) {
                v.push_back({x, y}); pii p = g1[x][y]; x = p.Fi, y = p.Se;
            }
            reverse(v.begin(), v.end());
            for(auto p : v)
            {
                put(p.Fi, p.Se); if(p.Fi == n / 2 && p.Se == m / 2) return 0;
                pii q = get(); if(check(p.Fi, p.Se, q.Fi, q.Se)) return put(q.Fi, q.Se), 0;
                
            }
        }
    }
    return 0;
}

参考文献：

[1] https://www.luogu.com.cn/article/dwwy1fks

题外话：

被本题解满篇的 \(\unicode{x2658}\) 和 \(\unicode{x265E}\) 震撼到了吗？

如果没有，那肯定被代码的弱智大分讨震撼到了吧。（虽然我抄的是参考文献的代码）

文章作者: q779
文章链接: https://q779.cn/2024/06/19/cf1201e2-knightmare-hard-ti-jie/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 q779 !
算法 构造 交互题 博弈论
评论
  目录