[20220115杂题选讲]Knight

Posted on | In ,

注意到一个二分图的性质，从而转化为博弈论简单题。

大意

在一个有障碍的 $n\times m$ 的国际象棋棋盘上，Alice 和 Bob 各有一只广义马，位置不同，且不在障碍上。

正常的马跳 $1\times 2$ 的日字，这里的马跳 $r\times c$ 的大日（？）字，其中 $r,c\in[1,1000]$。

任何一匹马在任何时候都不能跳到障碍或对方的马上。

如果一方无法走子，或无论怎么走子棋盘都将与之前的局面重复，则判此方负。

容易证明，游戏必在有限步内结束，且至少有一方有必胜策略，问谁有必胜策略？

$n,m\le 1000$。

source: 35th Petrozavodsk Programming Camp, Summer 2018; Day 8: Yuhao Du Contest 5, Grand Prix of Zhejiang, Thursday, August 30, 2018.

link: http://qoj.ac/contest/802/problem/2213

思路

首先对棋盘上的非障碍点连边，当且仅当能一步跳到才连上。

重要引理：无论 $r$ 和 $c$ 怎么取值，棋盘上皆可黑白染色，同色格内无法一步到达。

证明：假设有情况不能黑白染色，即棋盘上有奇环，那么考察环上一点 $P(0,0)$，走了一个奇环回到原点。

观察横坐标，$k_1r+k_2c=0$，显然 $2\not\mid k_1+k_2$，纵坐标 $k_3r+k_4c=0$ 同理。注意到 $|\Delta x|=r$ 的次数与 $k_1$ 奇偶性相同， 与 $k_4$ 奇偶性相同。故 $k_1\equiv k_4$，$k_2\equiv k_3$。不失一般性，令 $2\mid k_1,k_4$，则 $2\not\mid k_2,k_3$，故 $2\mid c,r$。

但是将 $r,c$ 同时除以 $2$，奇环不会改变，说明如果存在一种 $2\mid r,c$ 的情况，也必然存在一种对应的 $2\mid r,c$ 不成立的情况，矛盾。

所以棋盘是个二分图！

考虑分类讨论：

情况一

A 和 B 不在同一个连通块里，A 胜（除非 A 无可达点）。

策略：设 A 的初始点为 $A_0$，其中一个可到的点为 $A_1$，则 A 只需反复横跳，B 在跳了一次之后的每个点都不能再走了（不妨令 A,B 初始点颜色相同，则 A,B 颜色恒相同，B 所在连通块的每个点都最多在棋盘状态中出现一次），B 负。

情况二

A,B 在同一个连通块内：

先设 A,B 在同色格内，则 A 必胜：

策略：选择一个可到点 $A_1$，执行情况一的策略。注意到 B 无法阻挡 A，因为 A 每次跳时目标点都与 B 当前所在点异色。

若 A,B 在异色格，则 B 必胜，因为 A 走一步就转移到上一种 A,B 同色的情况了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

namespace mirai {

bool map[1010][1010];
bool dist[1010][1010];

int main(int argc, char** argv) {
  int n, m, r, c;
  std::scanf("%d%d%d%d", &n, &m, &r, &c);
  int x1, y1, x2, y2;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      char ch;
      std::scanf(" %c", &ch);
      if (ch == '@') {
        map[i][j] = true;
      }
      if (ch == 'A') {
        x1 = i;
        y1 = j;
      }
      if (ch == 'B') {
        x2 = i;
        y2 = j;
      }
    }
  }
  int move[8][2] = {{r, c}, {r, -c}, {-r, c}, {-r, -c}, {c, r}, {c, -r}, {-c, r}, {-c, -r}};
  std::queue<std::pair<int, int>> que;
  que.push({x1, y1});
  map[x1][y1] = true;
  bool updated = false;
  while (!que.empty()) {
    int x = que.front().first, y = que.front().second;
    que.pop();
    for (int i = 0; i < 8; ++i) {
//    std::printf("%d %d\n", x, y);
      int nx = x + move[i][0], ny = y + move[i][1];
      if (nx < 1 || nx > n || ny < 1 || ny > m) {
        continue;
      }
      if (map[nx][ny] == false) {
        dist[nx][ny] = !dist[x][y];
        if (nx == x2 && ny == y2 && !(x == x1 && x == x2)) {
          std::puts(dist[nx][ny] ? "Bob" : "Alice");
          return 0;
        }
        que.push({nx, ny});
        if (!(nx == x2 && ny == y2)) {
          map[nx][ny] = true;
        }
        updated = true;
      }
    } 
  }
  std::puts(updated ? "Alice" : "Bob");
  return 0;
}

}

int main(int argc, char** argv) {
  return mirai::main(argc, argv);
}