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

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 !
算法 构造 交互题 博弈论
评论
  目录