# 仅对角邻接的网格森林：奇偶拆分与三次方界

同时保留正交和对角边的模型另见[八邻接拓展](eight-neighbor.zh.md)，其证明使用方向词推广。

[English](diagonal-only.en.md) · [四邻接三次方证明](../proofs/cubic-bound.zh.md) · [补树障碍](../examples/tree-extension.zh.md) · [引用](../../../../../CITATION.md) · [研究目录](../README.md)

日期：2026-10-12。本文给出仅允许四个对角方向时的完整归约证明。这是已有四邻接结果的推论：两种奇偶类各自同构于四邻接整数网格，答案与候选检查次数可逐项对应，无需重新建立收费证明。

检索词：对角邻接、对角网格森林、奇偶拆分、坐标变换、平移匹配、三次方上界；diagonal-only grid forest, parity decomposition, lattice isomorphism, translation matching。

## 1. 模型与结论

棋盘为 $\{0,\ldots,n-1\}^2$，道路点集为 $F$，道路数为 $N=|F|$，实际移动数为 $m$。邻接和移动都只允许

$$
D=\{(1,1),(1,-1),(-1,1),(-1,-1)\}.
$$

道路之间保留全部这种边，并要求诱导图是森林。对角边不受两侧正交格是否为道路影响；两条边在格子内部几何相交不产生额外顶点。这里没有上下左右的边，也没有额外的“禁止穿角”规则。

起点必须完整执行移动前缀，失败后永久失效；候选列表只在首次出现相对位移时筛选。记这些筛选中逐候选检查的总次数为 $W$，不计初始读取道路。则

$$
\boxed{W\le(5n-3)N},\qquad
\boxed{T=O(n^2+m+nN)\subseteq O(n^3+m)}.
$$

空间为 $O(n^2)$；短移动序列还满足 $T=O(n^2+m+N\min(m,n))$。在 $m\ge n-1$ 时，该候选列表算法的最坏时间为 $\Theta(n^3+m)$。这不是所有可能算法的三次方下界。

补点扩充成单树时，跨奇偶类已有不可连通障碍；即使所有原点属于同一奇偶类，四邻接模型中的不可扩充反例族仍然保留。

## 2. 两种颜色各自变回四邻接

每次对角移动使坐标和改变零或正负二，因此保持 $x+y\pmod 2$。令

$$
F_p=\{(x,y)\in F:x+y\equiv p\pmod 2\},\qquad p\in\{0,1\}.
$$

两类之间没有边。对固定奇偶类定义

$$
\Phi_p(x,y)=(u,v)=\left(\frac{x+y-p}{2},\frac{x-y-p}{2}\right),
\qquad
\Phi_p^{-1}(u,v)=(u+v+p,u-v).
$$

这是整个该奇偶类与整数格点之间的双射。四种边和移动恰好变为：

| 原移动 | 变换后移动 |
| --- | --- |
| $(1,1)$ | $(1,0)$ |
| $(1,-1)$ | $(0,1)$ |
| $(-1,1)$ | $(0,-1)$ |
| $(-1,-1)$ | $(-1,0)$ |

逆变换也把每条四邻接边变成对角边，因此不会漏边或增加额外边。诱导图、连通分量、环与森林性质全部保留。

例如下面五个道路点全属于偶数类。右图把变换后的第二坐标整体加一；字母保持对应，点号表示未选中的位置。

```text
A . B        . A .
. C .   ->   B C D
D . E        . E .
```

左边中心与四角相连，右边中心与上下左右相连：它们是同一棵五点树的两种坐标表示。

变换后的棋盘不必是实心矩形，但每个坐标方向所占的整数范围都至多有 $n$ 个值：原来的和 $x+y$ 与差 $x-y$ 各落在长度 $2(n-1)$ 的区间内；固定奇偶后间隔为二，除以二后的跨度至多为 $n-1$。整体平移并在空缺处填障碍，就得到一个边长至多为 $n$ 的原四邻接实例。空奇偶类直接忽略。

## 3. 为什么答案和检查次数也完全对应

设原查询的某个相对位移为 $q=(a,b)$。由对角移动产生的位移满足 $a+b\equiv0\pmod2$。定义

$$
L(q)=\left(\frac{a+b}{2},\frac{a-b}{2}\right).
$$

对任意奇偶类中的起点 $s\in F_p$，都有

$$
\Phi_p(s+q)=\Phi_p(s)+L(q).
$$

所以每个移动前缀在原道路上合法，当且仅当变换后的前缀在相应道路像上合法；离开棋盘或遇到障碍都对应非道路。两个子问题使用同一条变换后的移动序列。

线性映射 $L$ 是单射，故“相对位移是否首次出现”也保持。把每次筛选前的候选按奇偶类分开，便得到两个子实例的候选列表；永久失效、重复位移、全部候选清空后的处理均对应。记第 $t$ 步后的答案为 $A_t$，则

$$
A_t=A_{t,0}+A_{t,1},\qquad W=W_0+W_1,\qquad N=N_0+N_1.
$$

对两个边长至多为原棋盘边长的森林应用[已有定理](../proofs/cubic-bound.zh.md)，得到

$$
W\le(5n-3)N_0+(5n-3)N_1=(5n-3)N.
$$

这是按道路数相加，并未多付一倍总道路预算。直接在原坐标维护候选也成立，实际程序不必创建两个新棋盘。初始扫描棋盘、读取并输出所有移动分别花平方和线性时间；结合每步至多检查全部道路的平凡界，就得到第 1 节的时间、空间及短序列结论。空道路或零次移动时检查次数均为零。

## 4. 三次方下界的迁移

反向考虑一个 $k\times k$ 的四邻接实例，定义

$$
\Psi(u,v)=(u+v,\ u-v+k-1).
$$

所有像点都位于 $\{0,\ldots,2k-2\}^2$，并属于同一个奇偶类。这个全局仿射映射把四邻接诱导图精确变为对角诱导图；单位移动也变为一次对角移动，答案和检查次数保持。

取偶数行全部铺满道路、其余行为空的四邻接实例，并连续向右移动 $k-1$ 次。道路是互不相邻的水平路径，有

$$
N=\left\lceil\frac{k}{2}\right\rceil k,\qquad
W=\left\lceil\frac{k}{2}\right\rceil
\sum_{j=1}^{k-1}(k-j+1)
=\left\lceil\frac{k}{2}\right\rceil\frac{(k-1)(k+2)}2
=\Theta(k^3).
$$

映射后方向为 $(1,-1)$，棋盘边长为 $2k-1$，故费用仍为边长的三次方。对任意充分大的目标边长，取 $k=\lfloor(n+1)/2\rfloor$ 并用障碍补齐棋盘。已有 $k-1\le n-1$ 次移动产生三次方费用；其后沿已走过的边来回补足任意更长移动序列。每步输出仍需常数时间，因此

$$
m\ge n-1\quad\Longrightarrow\quad T_{\mathrm{worst}}=\Theta(n^3+m).
$$

## 5. 森林补点成树：简单障碍与原反例族

若原森林同时包含两个奇偶类的点，则无论添加多少格点、扩大多少空间，都无法连通。例如 $(0,0)$ 与 $(0,1)$ 两个孤立点就已构成反例。路径中的每一步都保持奇偶性，补点无法改变这一事实。

若所有原点属于同一奇偶类，任何包含它们的单棵对角树也只能属于这一类。由于第 2 节的双射定义在整个无限格点集上，任意对角诱导树扩充都将逆映射为一个四邻接诱导树扩充。因此，[原四邻接模型中的不可扩充森林](../examples/tree-extension.zh.md)经第 4 节映射后仍然不可扩充，允许任意扩大棋盘也无济于事。

这同时迁移了两条大路径的障碍，以及线性数量、每棵线性大小、任取两棵都无法扩充成树的嵌套族。映射保留顶点数与分量，只将棋盘边长改变常数倍，所以两个线性量级均保持。这里仍要求固定原顶点位置并保留所有诱导边；未改动原反例的适用边界。

## 6. 复核范围、依赖与限制

一般结论由上述同构及已有四邻接证明推出。它不适用于“保留上下左右并加入对角线”的八邻接模型，也不直接涵盖依赖侧面障碍的禁止穿角规则。原题的题面、输入方向编码和标准程序保持四邻接定义；本文是独立拓展研究。

从仓库根目录运行 Python 3.10 或更高版本，只需标准库：

```text
python topics/simulation/grid-forest-matching/research/verify_diagonal_only.py --output tmp/grid-forest-matching/diagonal-only-results.json
```

[验证脚本](../verify_diagonal_only.py)与[发布的结果报告](../diagonal-only-results.json)记录：

- 边长一至十二的两个奇偶类，共 24 个棋盘类别：检查双射、诱导邻接与坐标范围。
- 边长一至三的全部 530 个道路点集：检查拆分前后的森林判定一致；其中 498 个是对角诱导森林。
- 对这 498 个森林枚举全部 256 条长度为四的移动序列，共 127,488 个组合：逐步核对答案、检查次数和上界，并以不跳过重复位移的直接模拟独立核对答案。这也覆盖这些序列的全部较短前缀。
- 迁移四个条带下界实例：目标棋盘边长分别为 7、15、31、63，检查次数分别为 18、140、1,080、8,432。

这些有限检查不穷举任意棋盘或任意长移动序列，也不重新验证原三次方收费证明。引用键为 `OccamGC2026DiagonalGridForest`，见[引用说明](../../../../../CITATION.md)。状态是“仓库提供文字证明”，不表示外部同行评审或形式化证明系统验证。