马能否走遍棋盘的可达性证明

马能否走遍棋盘的可达性证明

群友在讨论 P1443 马的遍历 这道题。很明显是广搜。

题目是在一个 $n\times m$ 的棋盘上给定马的起点，求它到每一个格子的最短步数；无法到达的位置输出 $-1$。

把每个格子看成一个顶点，每一次合法马步看成一条边，那么题目就是无权图上的单源最短路。直接从起点做 BFS 即可，时间复杂度为：

$$O(nm)$$

而题目本身要求输出 $nm$ 个答案，仅输出就至少需要：

$$\mathrm{\Omega }(nm)$$

所以对于原题，BFS 已经达到最优复杂度量级。

不过，继续考虑两个问题：

1. 如果只询问到某一个点的距离，是否存在直接公式？
2. 是否存在马永远到不了的点？

显然这两个问题必须区分有限棋盘与无限棋盘。

---

一、无限棋盘上的单点最短距离公式

将起点平移到原点 $(0,0)$，目标点记为 $(x,y)$。

由于马步关于坐标轴和直线 $y=x$ 对称，只需令：

$$a=max(|x|,|y|),b=min(|x|,|y|)$$

于是总有：

$$a\ge b\ge 0$$

在无限棋盘上，最短步数为：

$$D(a,b)=\{\begin{array}{ll}3,& (a,b)=(1,0)\\ 4,& (a,b)=(2,2)\\ d,& \text{其他情况}\end{array}$$

其中先计算：

$$d_0=max(\lceil \frac{a}{2}\rceil ,\lceil \frac{a+b}{3}\rceil )$$

再按照奇偶性修正：

$$d=\{\begin{array}{ll}{d}_0,& d_0\equiv a+b(\mathrm{mod}2)\\ d_0+1,& d_0\not\equiv a+b(\mathrm{mod}2)\end{array}$$

例如：

目标位移	最少步数
$(1,2)$	$1$
$(1,1)$	$2$
$(1,0)$	$3$
$(2,2)$	$4$
$(5,5)$	$4$

这个公式中的三个限制

马的一步位移为：

$$(\pm 1,\pm 2),(\pm 2,\pm 1)$$

首先，较大的坐标差每一步最多减少 $2$，因此：

$$d\ge \lceil \frac{a}{2}\rceil$$

其次，坐标绝对值之和每一步最多减少 $3$，因此：

$$d\ge \lceil \frac{a+b}{3}\rceil$$

所以：

$$d\ge max(\lceil \frac{a}{2}\rceil ,\lceil \frac{a+b}{3}\rceil )$$

最后，马每走一步，坐标和的奇偶性都会翻转。因为一步中坐标和的变化量一定是奇数：

$$(\pm 1)+(\pm 2)\equiv 1(\mathrm{mod}2)$$

因此，若走 $d$ 步到达 $(x,y)$，必须满足：

$$d\equiv x+y\equiv a+b(\mathrm{mod}2)$$

所以，当 $d_0$ 与 $a+b$ 奇偶性不同时，还需要再加一步。

两个特殊点 $(1,0)$ 与 $(2,2)$ 属于距离过小造成的局部例外，需要单独处理。

例如：

$$(1,0)=(1,2)+(2,-1)+(-2,-1)$$

因此从原点到 $(1,0)$ 可以三步到达，但不可能更少。

---

二、为什么这个公式不能解决原题

上面的公式针对的是无限棋盘。

原题中的棋盘存在边界，而无限棋盘上的最短路径可能会暂时跳出矩形区域。

例如，在无限棋盘上：

$$(1,1)\to (3,0)\to (2,2)$$

所以从 $(1,1)$ 到 $(2,2)$ 可以两步到达。

但在 $3\times 3$ 棋盘中，$(3,0)$ 已经越界，这条路径不合法。事实上，中心点 $(2,2)$ 没有任何合法马步与其他位置连接。

从左上角出发时，距离表为：

$0$	$3$	$2$
$3$	$-1$	$1$
$2$	$1$	$4$

因此：

$$\text{无限棋盘上的最短距离}\ne \text{有限棋盘上的最短距离}$$

有限棋盘中，边界会改变整张马步图的结构，所以原题仍应使用 BFS。

---

三、无限棋盘上有没有永远到不了的点

没有。

这个结论可以直接通过生成元证明。

把所有整数格点组成的集合视为加法群：

$${\mathbb{Z}}^2$$

马的一步能够产生的位移向量为：

$$(\pm 1,\pm 2),(\pm 2,\pm 1)$$

记这些向量生成的子群为：

$$H=⟨(\pm 1,\pm 2),(\pm 2,\pm 1)⟩$$

只需证明：

$$(1,0)\in H,(0,1)\in H$$

因为 $(1,0)$ 与 $(0,1)$ 生成整个 ${\mathbb{Z}}^2$。

首先：

$$(1,2)+(2,-1)+(-2,-1)=(1,0)$$

所以：

$$(1,0)\in H$$

对应路径为：

$$(0,0)\to (1,2)\to (3,1)\to (1,0)$$

其次：

$$(2,1)+(-1,2)+(-1,-2)=(0,1)$$

所以：

$$(0,1)\in H$$

对应路径为：

$$(0,0)\to (2,1)\to (1,3)\to (0,1)$$

于是，对任意整数点 $(x,y)$，都有：

$$(x,y)=x(1,0)+y(0,1)\in H$$

因此：

$$H={\mathbb{Z}}^2$$

即无限棋盘上，马可以到达任意整数格点。

---

四、尝试黑白染色

将棋盘按照 $x+y$ 的奇偶性染成黑白两色。

马每走一步，$x+y$ 的奇偶性都会翻转，因此格子颜色也会翻转。

所以，如果目标点与起点同色，则所需步数一定为偶数；如果目标点与起点异色，则所需步数一定为奇数。

即：

$$d\equiv \mathrm{\Delta }x+\mathrm{\Delta }y(\mathrm{mod}2)$$

但是，这只能限制步数的奇偶性，不能证明某个点不可达。

例如，$(1,0)$ 与原点异色，所以它必须经过奇数步到达；而它确实可以在三步后到达：

$$(0,0)\to (1,2)\to (3,1)\to (1,0)$$

因此在无限棋盘上，染色法约束步数奇偶，但不产生不可达点。

---

五、有限矩形棋盘什么时候连通

考虑一个没有障碍物的 $m\times n$ 矩形棋盘，不妨设：

$$1\le m\le n$$

结论为：

$$\boxed{{\displaystyle m\times n\text{ 的马步图连通}⟺(m,n)=(1,1)\text{，或 }m\ge 3\text{ 且 }(m,n)\ne (3,3)}}$$

换言之，除单格棋盘外，不连通的矩形棋盘只有：

$$1\times n,2\times n,3\times 3$$

下面分别证明。

---

六、$1\times n$ 棋盘不连通

如果棋盘只有一行，马不存在任何合法移动。

因为马的一步至少需要跨越两行或三行，而棋盘中只有一行。

因此当 $n>1$ 时，每个格子都是孤立点：

$$\boxed{{\displaystyle 1\times n(n>1)\text{ 不连通}}}$$

---

七、$2\times n$ 棋盘不连通

如果棋盘只有两行，马的一步不可能让行号变化 $2$，否则会越界。

因此，合法移动只能满足：

$$\mathrm{\Delta }\text{行}=\pm 1,\mathrm{\Delta }\text{列}=\pm 2$$

也就是说，列编号每次只能变化 $2$：

$$j\to j\pm 2$$

于是列编号的奇偶性保持不变。

第 $1$ 列	第 $2$ 列	第 $3$ 列	第 $4$ 列	第 $5$ 列	第 $6$ 列
奇	偶	奇	偶	奇	偶
奇	偶	奇	偶	奇	偶

从奇数列出发，永远到不了偶数列；从偶数列出发，永远到不了奇数列。

因此：

$$\boxed{{\displaystyle 2\times n\text{ 不连通}}}$$

这里的不变量是：

$$\boxed{{\displaystyle \text{列编号模 }2\text{ 的余数}}}$$

---

八、$3\times 3$ 棋盘不连通

考虑中心点 $(2,2)$。

从中心点出发，马无论走：

$$(\pm 1,\pm 2)$$

还是：

$$(\pm 2,\pm 1)$$

都会越界。

所以中心点没有任何邻点。由于马步可逆，也没有任何其他点能够到达中心点。

$\cdot$	$\cdot$	$\cdot$
$\cdot$	孤立点	$\cdot$
$\cdot$	$\cdot$	$\cdot$

因此：

$$\boxed{{\displaystyle 3\times 3\text{ 不连通}}}$$

---

九、$3\times 4$ 棋盘连通

下面给出一条经过全部十二个格子的合法路径。表格中的数字表示访问顺序：

$1$	$4$	$7$	$10$
$8$	$11$	$2$	$5$
$3$	$6$	$9$	$12$

按编号依次移动：

$$1\to 2\to 3\to \cdots \to 12$$

任意相邻两个编号所在位置的坐标差都为：

$$(1,2)\text{或}(2,1)$$

因此每一步都是合法马步。

所以：

$$\boxed{{\displaystyle 3\times 4\text{ 连通}}}$$

---

十、从 $3\times 4$ 推广到所有 $3\times n$

假设 $3\times k$ 已经连通，其中：

$$k\ge 4$$

现在向右增加第 $k+1$ 列。

新增的三个格子分别可以与旧棋盘中的格子通过一步马步相连：

$$(1,k+1)\leftrightarrow (3,k)$$

$$(2,k+1)\leftrightarrow (1,k-1)$$

$$(3,k+1)\leftrightarrow (1,k)$$

对应的坐标差分别为：

新增格子	旧棋盘中的邻点	坐标差
$(1,k+1)$	$(3,k)$	$(2,1)$
$(2,k+1)$	$(1,k-1)$	$(1,2)$
$(3,k+1)$	$(1,k)$	$(2,1)$

所以新增一列中的每个格子都接入了原来的连通块。

由数学归纳法：

$$\boxed{{\displaystyle 3\times n(n\ge 4)\text{ 全部连通}}}$$

---

十一、继续增加行数

假设 $k\times n$ 已经连通，其中：

$$k\ge 3,n\ge 4$$

现在向下增加第 $k+1$ 行。

对于新增行中的任意格子 $(k+1,j)$：

• 若 $j\le n-2$，则它与 $(k,j+2)$ 相连；
• 若 $j\ge n-1$，则它与 $(k,j-2)$ 相连。

上述两种连接的坐标差均为：

$$(1,2)$$

而 $n\ge 4$ 保证所选旧格子始终存在。

所以新增行中的每个格子都会接入原连通块。

由归纳法：

$$\boxed{{\displaystyle m\ge 3,n\ge 4\text{ 时，}m\times n\text{ 棋盘连通}}}$$

结合前面的三个反例，得到完整分类：

$$\boxed{{\displaystyle m\times n\text{ 的马步图连通}⟺(m,n)=(1,1)\text{，或 }m\ge 3\text{ 且 }(m,n)\ne (3,3)}}$$

其中默认：

$$m\le n$$

---

十二、结论

对于原题：

$$\boxed{{\displaystyle \text{有限棋盘上输出全部最短距离：使用 BFS，复杂度为 }O(nm)}}$$

对于无限棋盘上的单点最短距离：

$$\boxed{{\displaystyle \text{存在 }O(1)\text{ 公式}}}$$

对于无限棋盘上的可达性：

$$\boxed{{\displaystyle \text{马步向量生成 }{\mathbb{Z}}^2\text{，因此任意格点均可达}}}$$

对于有限矩形棋盘的连通性：

$$\boxed{{\displaystyle \text{除 }1\times n(n>1)、2\times n、3\times 3\text{ 外，其余矩形棋盘均连通}}}$$

__EOF__