[EC Final 2022] Chinese Checker

形式化题目

棋盘是一个由 $121$ 个格子组成的六角星，按行编号 $1\sim 17$ ，第 $r$ 行的格子数是

(1,2,3,4,\,13,12,11,10,\,9,\,10,11,12,13,\,4,3,2,1)\text{。}

行内格子从左到右编号 $1\sim L_r$ 。把第 $r$ 行第 $c$ 个格子放在坐标

(r,\;X),\qquad X = -(L_r-1) + 2(c-1)

处，则“同行”就是 $r$ 相同、 $X$ 差 $2$ ；另外两个轴向分别是 $(r,X)\to(r\pm 1,\,X\mp 1)$ 。于是每个格子都有 $6$ 个轴方向，相邻格之间恰好差

(0,+2),\;(0,-2),\;(+1,+1),\;(+1,-1),\;(-1,+1),\;(-1,-1)\text{。}

给定一个棋子集合 $S$ （ $121$ 个格子中的 $n$ 个）， $\lvert S\rvert = n$ 。一次 move 按如下规则进行：

先选定一颗棋子 $a$ ；
反复执行 step：沿某个轴向选另一颗棋子 $b$ 作支点，把 $a$ 移到它关于 $b$ 的对称格 $q = 2b - a$ 上。

一次 step 合法的条件是：

$a,b$ 在同一条轴线上（ $b$ 不必与 $a$ 相邻）；
连接 $a$ 与 $q$ 的线段上，除 $b$ 之外没有别的棋子；
$q$ 在棋盘内、且当前为空；
执行后 $a$ 不能回到这次 move 出发前所在的位置。

一次 move 至少包含一个 step，之后可以随时停下。棋子是不可分辨的，两次 move 相同 $\iff$ move 结束后所有棋子的位置集合相同。

求不同的 move 数。 $T\leqslant 100$ 。

暴力解法

思路

最直接的做法就是把题面逐字翻译，不做任何化简。

外层枚举移动的棋子 $a$ ；内层 DFS 枚举它走的每一步：把所有别的棋子 $b$ 都试一遍当支点，只要 $a,b$ 同轴，就沿着这条轴线逐格检查题面里的三条限制——中间除 $b$ 外没有别的棋子、对称格在盘内且为空、对称格不是 $a$ 这次的起点；三条都满足就走过去继续搜。

一个终局用一个“所有棋子所在格编号排好序”的 vector 表示，丢进 std::set 去重，最后 set 的大小就是答案。

代码

cpp

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:23
 * update_at: 2026-10-03 12:55
 *
 * P9723 [EC Final 2022] Chinese Checker —— 暴力对拍解
 *
 * 思路完全照抄题面，不做任何优化：
 *   1. 枚举移动的棋子 a；
 *   2. 从 a 的起点开始 DFS：枚举棋盘上每个别的棋子 b 当 pivot，
 *      若 a、b 连线平行于三个轴之一，就逐格检查题面的三条限制：
 *        - 除 b 外，a 到对称点的中间格必须为空；
 *        - 对称点 q = 2b - a 必须在盘内、且为空；
 *        - q 不能是 a 的起点 p0（不允许走回去）。
 *      满足就走一步，并且每一步之后都可以选择停下；
 *   3. 每个终局用"所有棋子所在格编号排序后的序列"表示，丢进 set 去重。
 *
 * 只有当 n 很小（生成器限制 n <= 8）时才能跑得动。
 */
#include <bits/stdc++.h>
using namespace std;

const int CELLS = 121 + 5;
const int OFFSET = 15;   // 轴向坐标 -12..12 平移到 0..30
const int WIDTH = 40;

int row_len[17] = {1, 2, 3, 4, 13, 12, 11, 10, 9, 10, 11, 12, 13, 4, 3, 2, 1};

int row_of[CELLS], x_of[CELLS];
int id_at[20][WIDTH];    // (行, 平移后的轴向坐标) -> 格编号，-1 表示不在盘上
int cell_cnt;

// 六个方向：(行变化, 轴向坐标变化)
int dr6[6] = {0, 0, 1, 1, -1, -1};
int dx6[6] = {2, -2, 1, -1, 1, -1};

int n;
int start_cell[20];      // 输入的棋子所在格
bool occ[CELLS];
bool reached[CELLS];    // 本次 a 已经到过的位置（避免绕圈无限递归）

set<vector<int> > finals;   // 去重后的终局集合

// u 沿方向 d 走一步的格编号，出界返回 -1
int next_cell(int u, int d) {
    int r = row_of[u] + dr6[d];
    int x = x_of[u] + dx6[d];
    if (r < 1 || r > 17) return -1;
    if (x < 0 || x >= WIDTH) return -1;
    return id_at[r][x];
}

void build_board() {
    memset(id_at, -1, sizeof(id_at));
    cell_cnt = 0;
    for (int r = 1; r <= 17; r++) {
        int len = row_len[r - 1];
        for (int c = 1; c <= len; c++) {
            int x = OFFSET - (len - 1) + 2 * (c - 1);
            cell_cnt++;
            id_at[r][x] = cell_cnt;
            row_of[cell_cnt] = r;
            x_of[cell_cnt] = x;
        }
    }
}

void dfs(int a, int pos, int p0) {
    // pos == p0 表示还没走出任何一步，不算一个 move；否则当前位置就是一个终局
    if (pos != p0) {
        vector<int> conf;
        for (int i = 1; i <= n; i++) {
            if (i == a) continue;              // 跳过正在移动的那颗棋子
            conf.push_back(start_cell[i]);
        }
        conf.push_back(pos);
        sort(conf.begin(), conf.end());
        finals.insert(conf);
    }

    for (int b = 1; b <= n; b++) {
        int bc = start_cell[b];
        if (b == a) continue;       // pivot 必须是另一颗棋子

        // 找 pos -> bc 的方向（必须同轴）
        int d = -1;
        for (int k = 0; k < 6; k++) {
            int cur = pos;
            while (true) {
                cur = next_cell(cur, k);
                if (cur == -1) break;
                if (cur == bc) { d = k; break; }
            }
            if (d != -1) break;
        }
        if (d == -1) continue;      // 不在同一条轴上

        // 数出 pos 到 bc 有多少步
        int step = 0, cur = pos;
        while (true) {
            cur = next_cell(cur, d);
            if (cur == -1) break;
            step++;
            if (cur == bc) break;
        }

        // 对称点 q = pos 沿 d 走 2*step 步
        cur = pos;
        bool bad = false;
        for (int t = 1; t <= 2 * step; t++) {
            cur = next_cell(cur, d);
            if (cur == -1) { bad = true; break; }
        }
        if (bad) continue;          // 对称点出界
        int q = cur;
        if (occ[q]) continue;       // 落点被占（含 q == bc 的情形）
        if (q == p0) continue;      // 不允许回到移动前的位置
        if (reached[q]) continue;   // 该位置之前已到过，再走只会重复

        // 中间格（严格夹在 pos 与 q 之间）除 bc 外必须为空
        bool ok = true;
        cur = pos;
        for (int t = 1; t <= 2 * step - 1; t++) {
            cur = next_cell(cur, d);
            if (cur == bc) continue;
            if (occ[cur]) { ok = false; break; }
        }
        if (!ok) continue;

        // 落子，继续搜索
        occ[pos] = false;
        occ[q] = true;
        reached[q] = true;
        dfs(a, q, p0);
        reached[q] = false;
        occ[q] = false;
        occ[pos] = true;
    }
}

int main() {
    build_board();
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        memset(occ, 0, sizeof(occ));
        for (int i = 1; i <= n; i++) {
            int r, c;
            scanf("%d %d", &r, &c);
            int len = row_len[r - 1];
            int x = OFFSET - (len - 1) + 2 * (c - 1);
            start_cell[i] = id_at[r][x];
            occ[start_cell[i]] = true;
        }
        finals.clear();
        for (int a = 1; a <= n; a++) {
            int p0 = start_cell[a];
            occ[p0] = false;                 // a 离开起点
            memset(reached, 0, sizeof(reached));
            reached[p0] = true;
            dfs(a, p0, p0);
            occ[p0] = true;
        }
        printf("%d\n", (int)finals.size());
    }
    return 0;
}

复杂度

设棋子数为 $n$ 。每次 DFS 最多访问 $121$ 个不同位置，每个位置要枚举 $n$ 个支点、每个支点最多沿一条轴线扫 $12$ 格、还要再沿轴线数 $O(1)$ 次，同时每记录一次终局都要 $O(n\log n)$ 建立并插入一个长度为 $n$ 的向量。整体大致是

O\big(n\cdot 121\cdot n\cdot 12 \cdot n\log n\big)

的量级。 $n$ 在 $8$ 以内时它是毫秒级的，可以作为对拍基线；但 $n$ 可以取到 $121$ ，这个做法完全无法运行。

瓶颈

瓶颈有两处，都来自“把 move 当成搜索树上的一条路径”：

状态爆炸。 $n=121$ 时用整盘棋子的位置去重，代价与状态数同阶，而状态数本身是指数级的。
没有发现“只有一个棋子会动”。暴力在搜索时把整盘局面当成状态，因此无法把“求可达集合”压缩成任何一个多项式规模的对象。

正解要做的，正是先把第 2 点吃透，把状态数压下去。

正解

思路

一、化简终局：一次 move 只是两个格子互换

题面明确规定：一次 move 从头到尾只有选定的那颗棋子 $a$ 在动，中途不能换 $a$ 。所以其余 $n-1$ 颗棋子的位置自始至终没有变化。

设 $a$ 的起点是 $p_0$ 。move 结束时，棋盘上“少了 $p_0$ 上的棋子、多了终点 $p$ 上的棋子”，其余格子一模一样。也就是说，终局完全由有序对 $(p_0, p)$ 决定， $p_0$ 必须是原本有棋子的格子， $p$ 必须满足

p \neq p_0,\qquad p \text{ 原本是空格。}

不同的 move 给出不同终局 $\iff$ 对应的 $(p_0,p)$ 不同。于是

\text{答案} \;=\; \sum_{\text{被占的 } p_0}\ \Bigl(\ \#\{p : a \text{ 从 } p_0 \text{ 出发能走到 } p\}\ -\ 1\Bigr),

减掉的 $1$ 就是 $p = p_0$ 这个“原地不动”的非法终局（move 必须至少一个 step）。

再注意一个细节：题目只禁止“回到这次 move 出发前的位置”，即 $p_0$ 只在终局时被禁止；中途绕回 $p_0$ 再走开是允许的，但那样也只是走回头路，不会带来新的终局。

二、固定 $p_0$ 之后，一步 step 到底能跳到哪里

把 $p_0$ 自己视为空格（它上面那颗棋子已经离开了），其余 $n-1$ 颗棋子全部当作障碍物。

对某个方向 $d$ ，沿 $p_0$ 出发一路数过去，把遇到的棋子按距离记下来。设最近的一颗在 $t_1$ 步处，第二近的一颗在 $t_2$ 步处，那么：

支点 $b$ 只能是 $t_1$ 处的这颗棋子。若选择更远的棋子，它到 $p_0$ 之间必然隔着 $t_1$ ，违反“除 $b$ 外中间不能有棋子”；
选定 $b$ 之后，对称格是 $q = p_0 + 2t_1\cdot d$ （而不是相邻格，题面特意说明支点不必与 $a$ 相邻）；
若 $t_2 \leqslant 2t_1$ ，那么“第二近”这颗棋子要么夹在 $p_0$ 与 $q$ 之间，要么正好占了 $q$ ，两种情形都非法；只有 $t_2 > 2t_1$ 时才可能合法；
最后还要 $q$ 在盘内且为空。

换句话说：每个方向至多只有一种 step 可选，而它由“最近的棋子”唯一确定。这就是把暴力里的双重枚举压成 $O(6)$ 的关键。

于是从 $p_0$ 出发，每一步都是确定的——这是一张 $121$ 个格子、每格至多 $6$ 条出边的有向图，答案就是它从 $p_0$ 能到达的格子数，一次 BFS 即可。

三、实现

棋盘很小，可以直接把它摆成一个二维数组。把轴向坐标 $X\in[-12,12]$ 平移成 $X+15\in[3,27]$ ：

id_of[r][x]：第 $r$ 行、轴向坐标 $x$ 的格子编号，-1 表示不在盘上；
on_board(r,x)： $1\leqslant r\leqslant 17$ ，且 $x$ 落在该行范围内（第 $r$ 行的范围是 $[15-(L_r-1),\,15+(L_r-1)]$ ）。

沿方向 $d$ 扫描时，只要一路走、记录前两颗棋子到起点的步数即可，最多扫 $6$ 步左右就会撞到第二颗棋子，代价极小。

对每个棋子跑一次 BFS，累加 reachable - 1。

四、样例推演

以样例 4（前 $4$ 行的小三角形，共 $10$ 颗棋子）为例，对每颗棋子跑一次 BFS，可达空格（写成 (行, 列)）如下。

$p_0$	可达空格	贡献
`(1,1)` `(2,1)` `(2,2)` `(4,1)` `(4,2)` `(4,3)` `(4,4)`	无	0
`(3,1)`	`(5,5)` `(5,7)`	2
`(3,2)`	`(5,6)` `(5,8)`	2
`(3,3)`	`(5,7)` `(5,9)`	2

合计 $2+2+2 = 6$ ，与样例输出一致。可以看出：只有 (3,1) 附近的棋子能借同行伙伴当支点弹出去，其它棋子被卡死。

再看样例 5，它把 (3,1) 换成了远处的 (5,7)，结果从 $6$ 变成 $13$ ：新增的 $7$ 个终局里，(5,7) 自己贡献 $2$ （可达 (3,1) 与 (5,5)），(3,3) 从 $2$ 涨到 $3$ 、(1,1) 从 $0$ 升到 $3$ 、(2,1) 升到 $1$ 、(4,2) 与 (4,3) 各升到 $1$ 。

这正是“每个棋子单独做 BFS 再相加”的直观体现：一颗远处的棋子可能同时落在好几颗棋子的轴线上，一次性给它们全部提供新的跳法，而这种叠加关系用“逐棋子求可达集”来处理是天然正确的。

代码

cpp

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:23
 * update_at: 2026-10-03 12:55
 *
 * P9723 [EC Final 2022] Chinese Checker
 *
 * 核心结论
 * --------
 * 一次 move 从头到尾只动 checker a，其它棋子全程不动。所以终局只是把
 * 「a 的起点 p0」和「a 的终点 p」这两个格子互换，而 p0 一定是原本有棋子的格子。
 * 因此一次 move 唯一对应一个空闲格子 p（p 从 p0 出发可达，且 p != p0），
 * 不同的 move 数 = sum over p0 in S ( 从 p0 出发能到达的空格数 - 1 )。
 *
 * 固定 p0 后怎么求可达集合
 * ------------------------
 * 把 p0 自己视为空（它已经离开了），其余 n-1 颗棋子当成障碍。
 * 一步 step 就是：选一个方向，找该方向上离 p0 最近的棋子 b 当 pivot，
 * 跳到关于 b 的对称点 q = 2b - p0，要求 q 在盘内且为空。
 *   * pivot 不必与 a 相邻，所以 q 可能离得很远；
 *   * "a 与 q 之间除 b 外没有其它棋子"等价于：该方向的第二近棋子必须在 q 之外。
 * 于是每个 p0 只需求一次 BFS，答案就是所有可达空格数之和。
 * 棋盘只有 121 格、6 个方向，T <= 100，轻松通过。
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int OFFSET = 15;          // 轴向坐标 -12..12 平移到 0..30
const int WIDTH = 40;           // 平移后坐标的取值范围
const int MAXC = 121 + 5;       // 棋盘上的格子总数 121

// 17 行的格子数（从上到下）
int row_len[17] = {1, 2, 3, 4, 13, 12, 11, 10, 9, 10, 11, 12, 13, 4, 3, 2, 1};

int id_of[20][WIDTH];           // (行, 平移后轴向坐标) -> 格子编号；-1 表示不在盘上
int cell_row[MAXC];             // 格子编号 -> 行号(1 起)
int cell_col[MAXC];             // 格子编号 -> 该行内第几个(1 起)
int cell_x[MAXC];               // 格子编号 -> 平移后的轴向坐标
int cell_cnt;

// 6 个方向。行变化 + 轴向坐标变化：
// 前两个是水平方向，中间两个是左下/右上，后两个是左上/右下。
int step_row[6] = {0, 0, 1, 1, -1, -1};
int step_dx[6]  = {2, -2, 1, -1, 1, -1};

bool occ[MAXC];                 // 当前局面下该格子是否有棋子
bool vis[MAXC];
int q[MAXC];                    // BFS 队列
int n;
int piece[MAXC];                // 第 i 颗棋子所在格子编号

// (行, 平移后轴向坐标) 是否在棋盘上
bool on_board(int row, int x) {
    if (row < 1 || row > 17) return false;
    int len = row_len[row - 1];
    // 该行的轴向坐标范围是 OFFSET-(len-1) .. OFFSET+(len-1)，步长 2
    return x >= OFFSET - (len - 1) && x <= OFFSET + (len - 1) && x < WIDTH;
}

// 建立棋盘：第 r 行有 row_len[r-1] 个格子，第 c 个格子的轴向坐标是 OFFSET-(len-1)+2*(c-1)
void build_board() {
    memset(id_of, -1, sizeof(id_of));
    cell_cnt = 0;
    for (int r = 1; r <= 17; r++) {
        int len = row_len[r - 1];
        for (int c = 1; c <= len; c++) {
            int x = OFFSET - (len - 1) + 2 * (c - 1);
            cell_cnt++;
            id_of[r][x] = cell_cnt;
            cell_row[cell_cnt] = r;
            cell_col[cell_cnt] = c;
            cell_x[cell_cnt] = x;
        }
    }
}

// 尝试从格子 u 沿方向 d 跳一步，能跳则把落点写入 np 并返回 true。
// 做法：一路扫过去，记下最近棋子的步数 first 和第二近棋子的步数 second。
//   * 没有棋子 -> 这个方向没有 pivot，不能走；
//   * second <= 2*first -> 第二近的棋子落在段内（或正好占了落点），不能走；
//   * 落点 = u 沿 d 走 2*first 步，若出界或已被占则不能走。
bool try_hop(int u, int d, int &np) {
    int r = cell_row[u], x = cell_x[u];
    int k = 0, first = -1, second = -1;
    while (true) {
        r += step_row[d];
        x += step_dx[d];
        k++;
        if (!on_board(r, x)) break;
        int v = id_of[r][x];
        if (occ[v]) {
            if (first == -1) first = k;
            else { second = k; break; }
        }
    }
    if (first == -1) return false;
    if (second != -1 && second <= 2 * first) return false;
    r = cell_row[u] + 2 * first * step_row[d];
    x = cell_x[u] + 2 * first * step_dx[d];
    if (!on_board(r, x)) return false;
    np = id_of[r][x];
    return !occ[np];                // 落点必须为空
}

// 以 p0 为起点 BFS（调用前需把 occ[p0] 置为 false），返回可达格子数（含 p0 自己）
int bfs_count(int p0) {
    memset(vis, 0, sizeof(bool) * (cell_cnt + 1));
    int head = 0, tail = 0;
    q[tail++] = p0;
    vis[p0] = true;
    int reached = 1;
    while (head < tail) {
        int u = q[head++];
        for (int d = 0; d < 6; d++) {
            int np = -1;
            if (!try_hop(u, d, np)) continue;
            if (vis[np]) continue;
            vis[np] = true;
            reached++;
            q[tail++] = np;
        }
    }
    return reached;
}

int main() {
    build_board();
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        memset(occ, 0, sizeof(occ));
        for (int i = 1; i <= n; i++) {
            int r, c;
            scanf("%d %d", &r, &c);
            int len = row_len[r - 1];
            int x = OFFSET - (len - 1) + 2 * (c - 1);
            piece[i] = id_of[r][x];
            occ[piece[i]] = true;
        }

        ll ans = 0;
        for (int i = 1; i <= n; i++) {
            int p0 = piece[i];
            occ[p0] = false;                // 移动的这颗棋子离开了起点
            ans += bfs_count(p0) - 1;       // 去掉"终点就是起点"这一种
            occ[p0] = true;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

复杂度

棋盘格数 $V = 121$ 。

预处理棋盘： $O(V)$ 。
对每个棋子跑一次 BFS：每次 BFS 遍历至多 $V$ 个格子，每个格子扫 $6$ 个方向，每个方向最多沿轴线扫 $O(13)$ 格。单次 $O(6V \cdot 13)$ ， $n$ 次即 $O(78Vn)$ 。
总计 $O(T \cdot 78 V n) \approx O(T \cdot 10^6)$ ，实际运行在毫秒级。

空间复杂度 $O(V)$ 。

总结

这道题的全部难度都在观察，写起来反而很短：

一次 move 只动一颗棋子 $\Rightarrow$ 终局与“起点、终点”这一对格子一一对应，于是“数不同 move”变成“数所有棋子各自的可达空格数”，答案可以逐棋子相加；
固定起点后，每个方向只有“最近的一颗棋子”能当支点，对称格是两步之外的格子，第二近的棋子不能落在线段内——于是每步只有 $6$ 种走法，直接 BFS。

得到的经验是：遇到“同一操作序列算一种结果”的计数题，先问“结果由什么唯一决定”。这里结果只由有序对 $(p_0,p)$ 决定，暴力里庞大的“整盘局面集合”就被压缩成了 $121$ 个格子上的可达性，这才是本题真正的解法入口。