一个有趣的小结论！

· · 个人记录

之前做题时遇到的。为什么你们天赋哥都能通过直觉感受出来它很对啊？

如果你想阅读人话，请看括号内。

定理 . 记 L=q_{-1,0},R=q_{1,0},U=q_{0,1},D=q_{0,1}，q 为形式记号，\mathbb D=\{L,R,U,D\}，二维平面的格点（视作向量）上有三种状态 c_{x,y}\in \{-1,0,1\}(x,y\in \Z)（其实分别代表空，格子，墙），保证只有有限个 (x,y) 满足 c_{x,y}\neq -1。记 S_0=\{(x,y)|c_{x,y}=0\},S=S_0\cup\{\bot\}，对于 s\in S,d\in \mathbb D，记 sd=\begin{cases}\bot&s=\bot\lor s=(x,y),d=q_{dx,dy},c_{x+dx,y+dy}=-1\\(x+dx,y+dy)&s=(x,y),d=q_{dx,dy},c_{x+dx,y+dy}=0\\(x,y)&s=(x,y),d=q_{dx,dy},c_{x+dx,y+dy}=1\end{cases}。（直观上，就是向对应方向走一步，如果是墙就不走，走到空就离开。）设 \mathcal D 为所有 \{L,R,U,D\} 的任意复合，d\in \mathcal D 的长度 |d| 为组成它的 L,R,U,D 的个数。称 s_1=(x_1,y_1)\in S_0 的可达区域 r(s_1)=r(x_1,y_1) 为 \{s_1d|d\in \mathcal D\land s_1d\neq \bot\}。称 s_1=(x_1,y_1),s_2=(x_2,y_2)\in S_0 是本质相同的（记作 P(s_1,s_2) 或 P(x_1,y_1,x_2,y_2)），当且仅当对于任意 d\in \mathcal D 有 s_1d=\bot 当且仅当 s_2d=\bot。（也就是对于相同的移动序列，两者是否离开地图是相同的。）如果对于一个 d 后件不成立，称 d 区分了 s_1,s_2。则 s_1,s_2 是本质相同的当且仅当以下三者之一成立：

证明 . 充分性显然，下证必要性。假定前两个条件不满足，只需证出第三个。

把 sd(s\in S,d\in \mathbb D) 的几种可能性予以称呼：s=\bot 为第零种情况，其余从上到下为第一、二、三种情况。对于 d\in \mathbb D，记 d^{-1} 为 L^{-1}=R,R^{-1}=L,U^{-1}=D,D^{-1}=U。对于 d=d_1d_2\cdots d_k(d_i\in \mathbb D)\in \mathcal D，记 d^{-1}=d_k^{-1}\cdots d_2^{-1}d_1^{-1}。对于 d\in \mathcal D，记 d^{n_0}(n_0\in \Z_{\ge 0}) 为 n_0 个 d 复合。

引理 1. 若 s\in S_0,d\in \mathcal D,sd=s'\in S_0，则对于任意最短的 d'\in \mathcal D 满足 sd'=s' 且 sd' 中只有第三种情况。

证明 . 显然没有第零、第一种情况。倘若有第二种情况，假若是在 d'=d_0d_1d_2(d_0,d_2\in \mathcal D,d_1\in \mathbb D) 时 (sd_0)d_1 出现了第二种情况，则显然有 sd_0d_2=s'，与最短性矛盾。故该 d' 只有第三种情况。

推论 1.1 若 s\in S_0,d\in \mathcal D,sd=s'\in S_0，则存在 d'\in \mathcal D 满足 sd'=s' 且 sd' 中只有第三种情况。（如果能到达，一定可以不撞墙到达。）

引理 2. 若 s\in S_0,d\in \mathcal D,sd=\bot，则对于任意最短的 d'\in \mathcal D 满足 sd'=\bot 且 sd' 中除了最后一步是第一种情况，只有第三种情况。

证明 . 显然最后一步不是第零种情况，否则可以去掉。剩下的部分套用引理 1. 的结论。（注意最短路的前缀一定是最短路。）

推论 2.1 若 s\in S_0,d\in \mathcal D,sd=\bot，则存在 d'\in \mathcal D 满足 sd'=\bot 且 sd' 中除了最后一步是第一种情况，只有第三种情况。（如果能走到空，一定可以不撞墙走到空。）

引理 3. 若 s_A\in S_0,s_B\in r(s_A)，则 s_A\in r(s_B)。（可达性是对称的。）

证明 . 由引理 1.，可以任取一个 d 满足 s_Ad=s_B 且只涉及第三种情况。设 d=d_1d_2\cdots d_k(d_i\in \mathbb D)，不难验证 s_Bd^{-1}=s_A，故原命题成立。

引理 4. 对于 s_A\in S_0,s_B\in r(s_A)，若存在 d\in \mathcal D 满足 s_Bd=\bot，则存在 d'\in \mathcal D 满足 s_Ad'=\bot。

证明 . 设 s_B=s_Ad_0，任取符合条件的 d，则取 d'=d_0d 符合条件。

推论 4.1 s_A\in S_0,s_B\in r(s_A)，若存在 d\in \mathcal D 满足 s_Ad=\bot，则存在 d'\in \mathcal D 满足 s_Bd'=\bot。

引理 5. 若 s_A,s_B 本质相同，d\in \mathcal D 满足 s_Ad\neq \bot，则 s_Bd\neq \bot，且 s_Ad 和 s_Bd 本质相同。

证明 . 依定义。

引理 6. 本质相同是等价关系。

证明 . 依定义。

接下来证明存在 d_1,d_2\in\mathcal D，满足 s_1d_1=s_2d_2=\bot。（两者均可走到空）若不然，因为不符合条件 I，不妨设不存在 d_1\in \mathcal D 满足 s_1d_1=\bot，而存在 d_2\in \mathcal D 满足 s_2d_2=\bot，则任取一个可能的 d_2 则有 s_1d_2\neq \bot 而 s_2d_2=\bot，故 d_2 区分了 s_1,s_2。与题设矛盾，故原命题成立。

因为条件 II 不成立，容易证明可以取最短的 d\in \mathcal D 满足 s_1d\neq \bot,s_2d\neq\bot，存在 q_{dx,dy}\in \mathbb D，c_{s_1d+(dx,dy)}\neq c_{s_2d+(dx,dy)}。那么因为 s_1d 和 s_2d 本质相同，不符合条件 I（推论 4.1）和条件 II（直接走 q_{dx,dy}），且用类似的方法可以证明 s_1d,s_2d 都只涉及第三种情况（如果某一步一个涉及了第二种情况作另一个没有则它们周围的 c 不一样，更短，否则都可以删去这一步），因此有 s_1d-s_1=s_2d-s_2，故容易证明对于 s_1d,s_2d 满足要求的 x_{L1},x_{R1},y_{L1},y_{R1},x_{L2},x_{R2},y_{L2},y_{R2},u,d,l,r 仍然符合条件。因此，我们可以从 s_1d,s_2d 开始证明，也就是无妨设存在 q_{dx,dy}\in \mathbb D，满足 c_{s_1+(dx,dy)}\neq c_{s_2+(dx,dy)}。而且，无妨设 (dx,dy)=(1,0)。

任取最短的 d\in\mathcal D，满足 s_1d=\bot。显然有 s_2d=\bot。下证这个 d 也满足它是满足 s_2d=\bot 的最短的 d。若不然，存在更短的 d'，满足 s_2d'=\bot，则 s_1d'=\bot，与 d 的最短性矛盾。因此 d 同时是满足 s_1d=\bot 的最短者和满足 s_2d=\bot 的最短者。

因为 c_{s_1+(1,0)}\neq c_{s_2+(1,0)}，若其中一者为 -1，则 q_{dx,dy} 就可以将它们区分开，因此一者为 1 一者为 0。无妨设 c_{s_1+(1,0)}=1 而 c_{s_2+(1,0)}=0。

设 m=\min \{q|q\in \Z_{\ge 0},c_{s_2+(q,0)}\neq 0\}。显然 m 是存在的，因为只有有限个不为 -1 的格子。根据条件有 m\ge 2，记 s_{R}=s_2+(m,0)，则 c_{s_{R}}=1。否则，如果是 -1，则 R^m 就可以区分 s_1,s_2，与题设矛盾。

对于任意 0\le k<m\in \N，有 s_1R^k,s_2R^k 本质相同。而 s_1R^k=s_1,s_2R^k=s_2+(k,0)，因此它们全部本质相同。对于 k=1,2,\cdots,m，记 t_k=s_2+(k-1,0)。

根据相同的论证，可以得出 d 同时也是所有 t_k 的最短满足 t_kd=\bot 的 d。下证 d 中没有 L。若不然，设 d=d_ALd_B(d_A,d_B\in \mathcal D)，则 t_1d_ALd_B=t_2d_ALd_B=\bot，而根据最短性在 L 之前都只有第三种情况，那么有 t_1d_A=t_2d_A+(-1,0)，故 t_2d_AL=t_1d_A，因此 t_1d_Ad_B=t_2d_ALd_B=\bot，与最短性矛盾。再证 d 中没有 R。若不然，设 d=d_ARd_B(d_A,d_B\in \mathcal D)，则 t_1d_ARd_B=t_2d_ARd_B=\bot，而根据最短性在 R 之前都只有第三种情况，那么有 t_2d_A=t_1d_A+(1,0)，故 t_1d_AR=t_2d_A，因此 t_2d_Ad_B=t_1d_ARd_B=\bot，与最短性矛盾。因此 d 中没有 L,R。

假若 d 中同时有 U,D，则必然存在相邻的 U,D，而若只涉及第三种情况，对于任何满足条件的 s\in S 都有 sUD=s（或 sDU=s），因此可以删去，与最短性矛盾。因此 d 中只有 U 或只有 D。无妨设 d 中只有 U。设 d=U^n，有 \forall s_0\in \{s_1,t_1,t_2,\cdots,t_m\},c_{s_0+(0,n)}=-1,\forall j=0,1,\cdots,n-1,c_{s_0+(0,j)}=0。

（用人话回顾一下之前我们证出来了什么：一些显然的引理，以及不妨假设盘面必然类似下图的样子。

....
.i..
.o..
.o..
.sx.
....

......
.iii..
.ooo..
.ooo..
.soox.
......

其中 x 为墙，i 为空，o 为格子，. 为未知。）

可以归纳地证明 c_{s_R+(0,k)}=1(k=0,1,\cdots,n-1)。显然 k=0 时成立。若已知 k 时成立，且 k+1\le n-1。如果 c_{s_R+(0,k+1)}=-1，那么容易验证 U^{k+1}R 可以区分 t_{m-1} 和 t_m。如果 c_{s_R+(0,k+1)}=0，那么容易验证 U^{k+1}RDLU^{n-k-1} 可以区分 t_{m-1} 和 t_m。因此 c_{s_R+(0,k+1)}=1。

同理可以归纳地证明 c_{s_1+(1,k)}=1(k=0,1,\cdots,n-1)。显然 k=0 时成立。若已知 k 时成立，且 k+1\le n-1。如果 c_{s_1+(1,k+1)}=-1，那么容易验证 U^{k+1}R 可以区分 s_1 和 t_m。如果 c_{s_1+(1,k+1)}=0，那么容易验证 U^{k+1}RDLU^{n-k-1} 可以区分 s_1 和 t_m。因此 c_{s_R+(1,k+1)}=1。

（说人话就是通过一些具体的构造，我们已经证完了右上角长啥样了。）

接下来向左看吧！令 f_2=\min\{f|f\in \Z_{\ge 0},c_{s_2-(f,0)}\neq 0\}，f_1=\min\{f|f\in \Z_{\ge 0},c_{s_1-(f,0)}\neq 0\}。记 a_i(i=1,2,\cdots,f_1)=s_1-(i-1,0),b_i(i=1,2,\cdots,f_2)=s_2-(i-1,0)。

首先有 c_{s_2-(f_2,0)}=1。如果 c_{s_2-(f_2,0)}=-1，那么 L^{f_2} 可以区分 t_1 和 t_2。其次有 c_{s_1-(f_1,0)}=1。如果 c_{s_1-(f_1,0)}=-1，那么 L^{f_1} 可以区分 s_1 和 s_2。

那么因为 t_1(=s_2),t_2 本质相同，必然有 t_1L^n=b_{n+1},t_2L^n=b_n(n=1,2,\cdots,f_2-1) 本质相同，根据传递性必然有所有 b_i 都和 b_1=s_2 本质相同。那么也必然有所有 a_i 都和 s_2 本质相同，因为 a_i=s_1L^{i-1} 必然和 b_{\min(i,f_2)}=s_2L^{i-1} 本质相同。因此立刻可以推出有 \forall s_0\in \{a_1,a_2,\cdots,a_{f_1},b_1,b_2,\cdots,b_{f_2},t_1,t_2,\cdots,t_m\},c_{s_0+(0,n)}=-1,\forall j=0,1,\cdots,n-1,c_{s_0+(0,j)}=0。记集合 Q=\{a_1,a_2,\cdots,a_{f_1},b_1,b_2,\cdots,b_{f_2},t_1,t_2,\cdots,t_m\}。

那么我们立刻可以同理推得对于所有 k=0,1,\cdots,n-1，c_{a_{f_1}+(-1,k)}=c_{b_{f_2}+(-1,k)}=1。

（用人话回顾一下之前我们证出来了什么：一些显然的引理，以及不妨假设盘面必然类似下图的样子。

......
.iii..
xooox.
xooox.
xooox.
......

...........
.iiiiiiii..
xoooooooox.
xoooooooox.
xoooooooox.
...........

其中 x 为墙，i 为空，o 为格子，. 为未知。而且，两个图中最后一行的每个 o 本质相同）

接下来向下进发。令 w=\min\{w_0|w_0\in \Z_{\ge 0},c_{s_2+(0,-w_0)}\neq 0\}。令 C=c_{s_2+(0,-w)}。那么对于 k=0,1,\cdots,w-1 有 c_{s_2+(0,-k)}=0 而 c_{s_2+(0,-w)}=C。接下来将证明对于任何 s_0\in Q，有对于 k=0,1,\cdots,w-1 有 c_{s_0+(0,-k)}=0 而 c_{s_0+(0,-w)}=C。

若不然，令 w'=\min\{w_0|w_0\in \Z_{\ge 0},c_{s_0+(0,-w_0)}\neq 0\}。令 C'=c_{s_0+(0,-w)}。倘若 C'\neq C，无妨设 C'=1 而 C=-1，那么 D^{w} 就可以区分 s_0 和 s_2，矛盾。否则，若 w'\neq w，若 C'=C=-1，则 D^{\min(w,w')} 可以区分 s_0 和 s_2，矛盾。若 C'=C=1，则 D^{\min(w,w')+1}U^{\min(w,w')+n} 可以区分 s_0 和 s_2，矛盾。综上，w'=w,C'=C，故原命题成立。

接下来可以以与之前完全一致的方式证明对于任何 k=0,1,\cdots,C-1，有 c_{t_m+(1,-k)}=c_{b_{f_2}+(-1,-k)}=c_{s_1+(1,-k)}=c_{a_{f_1}+(-1,-k)}=1。

至此，若 s_1=(x_1,y_1),s_2=(x_2,y_2)，取 x_{L1}=x_1-f_1+1,x_{R1}=x_1,y_{L1}=y_1-w+1,y_{R1}=y_1+n-1,x_{L2}=x_2-f_2+1,x_{R2}=x_2+m-1,y_{L2}=y_2-w+1,y_{R2}=y_2+n-1,l=r=1,u=-1,d=C 即可。证毕！