本解法では最短遷移を計算することが可能です。

解法

\(i\) step 後に存在可能な点の集合 \(S _ i\) は \(l_x\leq r_x, l_x\equiv r_x \equiv s_x\ (\mathrm{mod}\ 2)\) および \(l_y\leq r_y, l_y\equiv r_y \equiv s_y\ (\mathrm{mod}\ 2)\) を満たす整数 \(l_x,l_y,r_x,r_y\) を用いて次のように表示できます。以降、合同式の法は全て \(2\) なので省略します。

\[ S _ i = \lbrace (x, y) \mid l _ x \leq x \leq r _ x \land l _ y \leq y \leq r _ y \land x \equiv s _ x \land y \equiv s _ y\rbrace. \]

証明したい命題を \(P(i)\) として数学的帰納法で証明します。

1. \(P(0)\)
   \(S _ 0 = \lbrace (s _ x, s _ y)\rbrace\) なので、\(l_x=r_x=s_x,l_y=r_y=s_y\) とすればよいです。

2. \(P(i) \Rightarrow P(i + 1)\ (i \geq 0)\)
   仮定 \(P(i)\) より \(l_x\leq r_x, l_x\equiv r_x \equiv s_x\) および \(l_y\leq r_y, l_y\equiv r_y \equiv s_y\) を満たす整数 \(l_x,l_y,r_x,r_y\) が存在して次が成り立ちます。

   \[S _ i = \lbrace (x, y) \mid l _ x \leq x \leq r _ x \land l _ y \leq y \leq r _ y \land x \equiv s _ x\ (\mathrm{mod}\ 2) \land y \equiv s _ y\ (\mathrm{mod}\ 2)\rbrace.\]

   集合 \(T\) を以下で定めます。

   \[T = \lbrace (x, y) \mid 2a - r _ x \leq x \leq 2b - l _ x \land 2c - r _ y \leq y \leq 2d - l _ y \land x \equiv s _ x\ (\mathrm{mod}\ 2) \land y \equiv s _ y\ (\mathrm{mod}\ 2)\rbrace.\]

   このとき、\(S_{i+1}=T\) であること、すなわち \(S_{i+1}\subseteq T\) かつ \(S_{i+1}\supseteq T\) であることを示します。

   • \(S _ {i + 1} \subseteq T\) の証明
     任意に \((x,y)\in S_{i+1}\) を取ります。このとき、ある \((x_0,y_0)\in S_i\) と整数 \(m_x, m_y \ (a\leq m_x\leq b, c\leq m_y\leq d)\) が存在して次を満たします:

     \[\begin{aligned}x&=2m_x-x_0, \\ y&=2m_y-y_0.\end{aligned}\]

     いま \(l_x \leq x_0 \leq r_x\) と \(l_y\leq y_0\leq r_y\) が成り立っているので、\(2a - r _ x \leq x \leq 2b - l _ x \) および \(2c - r _ y \leq y \leq 2d - l _ y\) が従います。

     また、仮定より \(x_0\equiv s_x\ (\mathrm{mod}\ 2)\) と \(y_0\equiv s_y\ (\mathrm{mod}\ 2)\) が成り立っているので、\(x\equiv 2m_x-x_0\equiv x_0\ (\mathrm{mod}\ 2)\) と\(y\equiv 2m_y-y_0\equiv y_0\ (\mathrm{mod}\ 2)\) が従います。

     以上で \((x,y)\in T\) が示せました。

   • \(S _ {i + 1} \supseteq T\) の証明
     任意に \((x, y)\in T\) を取ります。このとき、次が成り立ちます。

     \[\begin{aligned}2a - r _ x \leq x \leq 2b - l _ x, \\ 2c - r _ y \leq y \leq 2d - l _ y, \\ x \equiv s _ x\ (\mathrm{mod}\ 2), \\ y \equiv s _ y\ (\mathrm{mod}\ 2). \end{aligned}\]

     ここで \(m_x=\max(a, (l_x+x)/2),m_y=\max(c,(l_y+y)/2)\) と定義します。\(x\equiv s_x \equiv l_x\) と \(y\equiv s_y \equiv l_y\) より \(m_x,m_y\) は整数です。

     また \((x_0, y_0) = (2m_x-x, 2m_y-y)\) とすると \(l_x \leq x_0\) および \(l_y \leq y_0\) が成り立ちます。\(2a-r_x\leq x\) より \(2a-x\leq r _ x\) なので \(x_0\leq r_x\) であり、同様に \(y_0\leq r_y\) も分かります。\(x_0\equiv x\equiv s_x, y_0\equiv y\equiv s_y\) なので結局 \((x_0, y_0)\in S_i\) です。

     さて、\(m_x, m_y\) の定義より \(a\leq m_x\) と \(c\leq m_y\) です。\(x\leq 2b-l_x\) より \((l_x+x)/2\leq b\) であり、同様に \((l_y+y)/2 \leq d\) です。問題の制約より \(a\leq b, c\leq d\) なので、\(a\leq m_x\leq b, c\leq m_y\leq d\) が成り立ちます。

     以上より、点 \((x, y)\) と点 \((x_0, y_0) \in S_i\) は点 \((m_x, m_y)\in R\) を中心として対称です。これは \((x,y)\in S_{i+1}\) であることを示しています。

   \(2a-r_x \leq 2b-l_x, 2c-r_y\leq 2d-l_y\) や \(2a-r_x\equiv 2b-l_x\equiv s_x, 2c-r_y\equiv 2d-l_y\equiv s_y\) も仮定から容易に示せます。以上で \(P(i)\Rightarrow P(i+1)\) が示されました。

以上 1, 2 より任意の非負整数 \(i\) に対して \(P(i)\) が成り立ちます。

証明で述べた通り、\(l_x,l_y,r_x,r_y\) に対して \(S_{i+1}\) は次の表示を持ちます。

\[S_{i+1} = \lbrace (x, y) \mid 2a - r _ x \leq x \leq 2b - l _ x \land 2c - r _ y \leq y \leq 2d - l _ y \land x \equiv s _ x\ (\mathrm{mod}\ 2) \land y \equiv s _ y\ (\mathrm{mod}\ 2)\rbrace.\]

即ち、以下のようにして \(l_x,l_y,r_x,r_y\) を (同時に) 更新することを繰り返せば \(S _ 0, S _ 1, \ldots, S _ {1000000}\) を得ることができます。

\[\begin{aligned} l_x &\leftarrow 2a-r_x, \\ r_x &\leftarrow 2b-l_x, \\ l_y &\leftarrow 2c-r_y, \\ r_y &\leftarrow 2d-l_y. \end{aligned}\]

\((t_x, t_y)\in S _ i\) となるか \(i = 1000001\) となるまで \(S _ i\) を更新し、後ろから遷移列を構築することで本問題を解くことができます。

遷移列の構築において \(1\) つ前の点を得るときは証明内で行ったのと同様に \(m_x=\max(a, (l_x+x)/2),m_y=\max(c,(l_y+y)/2)\) を中心として選ぶとよいです。

実装: C++ (GCC 9.2.1)