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

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

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

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

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

\[O(nm) \]

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

\[\Omega(nm) \]

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

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

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

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

---

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

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

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

\[a=\max(|x|,|y|),\qquad b=\min(|x|,|y|) \]

于是总有：

\[a\ge b\ge 0 \]

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

\[D(a,b)= \begin{cases} 3, & (a,b)=(1,0) \\[6pt] 4, & (a,b)=(2,2) \\[6pt] d, & \text{其他情况} \end{cases} \]

其中先计算：

\[d_0= \max\left( \left\lceil\frac{a}{2}\right\rceil, \left\lceil\frac{a+b}{3}\right\rceil \right) \]

再按照奇偶性修正：

\[d= \begin{cases} d_0, & d_0\equiv a+b\pmod 2 \\[6pt] d_0+1, & d_0\not\equiv a+b\pmod 2 \end{cases} \]

例如：

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

这个公式中的三个限制

马的一步位移为：

\[(\pm1,\pm2),\qquad(\pm2,\pm1) \]

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

\[d\ge \left\lceil\frac{a}{2}\right\rceil \]

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

\[d\ge \left\lceil\frac{a+b}{3}\right\rceil \]

所以：

\[d\ge \max\left( \left\lceil\frac{a}{2}\right\rceil, \left\lceil\frac{a+b}{3}\right\rceil \right) \]

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

\[(\pm1)+(\pm2)\equiv1\pmod 2 \]

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

\[d\equiv x+y\equiv a+b\pmod 2 \]

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

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

例如：

\[(1,0)=(1,2)+(2,-1)+(-2,-1) \]

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

---

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

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

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

例如，在无限棋盘上：

\[(1,1)\rightarrow(3,0)\rightarrow(2,2) \]

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

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

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

\(0\)	\(3\)	\(2\)
\(3\)	\(-1\)	\(1\)
\(2\)	\(1\)	\(4\)

因此：

\[\text{无限棋盘上的最短距离}\neq\text{有限棋盘上的最短距离} \]

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

---

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

没有。

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

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

\[\mathbb Z^2 \]

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

\[(\pm1,\pm2),\qquad(\pm2,\pm1) \]

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

\[H=\left\langle(\pm1,\pm2),(\pm2,\pm1)\right\rangle \]

只需证明：

\[(1,0)\in H,\qquad(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)\rightarrow(1,2)\rightarrow(3,1)\rightarrow(1,0) \]

其次：

\[(2,1)+(-1,2)+(-1,-2)=(0,1) \]

所以：

\[(0,1)\in H \]

对应路径为：

\[(0,0)\rightarrow(2,1)\rightarrow(1,3)\rightarrow(0,1) \]

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

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

因此：

\[H=\mathbb Z^2 \]

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

---

四、尝试黑白染色

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

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

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

即：

\[d\equiv \Delta x+\Delta y\pmod 2 \]

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

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

\[(0,0)\rightarrow(1,2)\rightarrow(3,1)\rightarrow(1,0) \]

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

---

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

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

\[1\le m\le n \]

结论为：

\[\boxed{ m\times n\text{ 的马步图连通} \iff (m,n)=(1,1) \text{，或 } m\ge3\text{ 且 }(m,n)\neq(3,3) } \]

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

\[1\times n,\qquad 2\times n,\qquad 3\times3 \]

下面分别证明。

---

六、\(1\times n\) 棋盘不连通

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

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

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

\[\boxed{1\times n\ (n>1)\text{ 不连通}} \]

---

七、\(2\times n\) 棋盘不连通

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

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

\[\Delta\text{行}=\pm1,\qquad \Delta\text{列}=\pm2 \]

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

\[j\rightarrow j\pm2 \]

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

第 \(1\) 列	第 \(2\) 列	第 \(3\) 列	第 \(4\) 列	第 \(5\) 列	第 \(6\) 列
奇	偶	奇	偶	奇	偶
奇	偶	奇	偶	奇	偶

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

因此：

\[\boxed{2\times n\text{ 不连通}} \]

这里的不变量是：

\[\boxed{\text{列编号模 }2\text{ 的余数}} \]

---

八、\(3\times3\) 棋盘不连通

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

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

\[(\pm1,\pm2) \]

还是：

\[(\pm2,\pm1) \]

都会越界。

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

\(\cdot\)	\(\cdot\)	\(\cdot\)
\(\cdot\)	孤立点	\(\cdot\)
\(\cdot\)	\(\cdot\)	\(\cdot\)

因此：

\[\boxed{3\times3\text{ 不连通}} \]

---

九、\(3\times4\) 棋盘连通

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

\(1\)	\(4\)	\(7\)	\(10\)
\(8\)	\(11\)	\(2\)	\(5\)
\(3\)	\(6\)	\(9\)	\(12\)

按编号依次移动：

\[1\rightarrow2\rightarrow3\rightarrow\cdots\rightarrow12 \]

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

\[(1,2)\quad\text{或}\quad(2,1) \]

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

所以：

\[\boxed{3\times4\text{ 连通}} \]

---

十、从 \(3\times4\) 推广到所有 \(3\times n\)

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

\[k\ge4 \]

现在向右增加第 \(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{3\times n\quad(n\ge4)\text{ 全部连通}} \]

---

十一、继续增加行数

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

\[k\ge3,\qquad n\ge4 \]

现在向下增加第 \(k+1\) 行。

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

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

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

\[(1,2) \]

而 \(n\ge4\) 保证所选旧格子始终存在。

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

由归纳法：

\[\boxed{m\ge3,\ n\ge4\text{ 时，}m\times n\text{ 棋盘连通}} \]

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

\[\boxed{ m\times n\text{ 的马步图连通} \iff (m,n)=(1,1) \text{，或 } m\ge3\text{ 且 }(m,n)\neq(3,3) } \]

其中默认：

\[m\le n \]

---

十二、结论

对于原题：

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

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

\[\boxed{\text{存在 }O(1)\text{ 公式}} \]

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

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

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

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