大通りを使わない場合

この場合、解は \((|S_x-G_x|+|S_y-G_y|) \times K\) となります。

大通りを使う場合

以下、\(x,y\) 座標のどちらかが \(B\) の倍数であるような格子点を良い格子点と呼ぶこととします。また、\(x,y\) 座標の両方が \(B\) の倍数であるような格子点をとても良い格子点と呼ぶこととします。

始めに通る良い格子点と、最後に通る良い格子点を全探索します。

始めに通る良い格子点の候補は、\((S_x,S_y)\) から上下左右のいずれかの方向に進み始めて大通りにぶつかったところとなります。

例えば、\(B=3,(S_x,S_y)=(1,1)\) の場合、候補は \((1,3),(1,0),(0,1),(3,1)\) のいずれかとなります。

これ以外の良い格子点 \(A\) を初めて通る時、上記のいずれかの格子点を先に通ることにより \(A\) により早く到達することができることから証明できます。

最後に通る格子点の候補も同様です。

より、\((S_x,S_y),(G_x,G_y)\) が両方良い格子点の場合を解けばよいです。

もし \((S_x,S_y),(G_x,G_y)\) 間をマンハッタン距離で大通りだけを使い移動できるならばそれが最適です。

\((S_x,S_y),(G_x,G_y)\) の少なくともどちらかがとても良い格子点の場合はそのような移動が可能であるため、以降 \((S_x,S_y),(G_x,G_y)\) は両方とても良い格子点ではないとします。

マンハッタン距離で大通りだけを使い移動できる条件は、以下のいずれかを満たすことです。

• \(S_x \bmod N = 0\) かつ \(G_y \bmod N = 0\) のとき
• \(S_y \bmod N = 0\) かつ \(G_x \bmod N = 0\) のとき
• \(S_x \bmod N = 0\) かつ \(G_x \bmod N = 0\) かつ \(\lfloor \frac{S_y}{B} \rfloor \neq \lfloor \frac{G_y}{B} \rfloor\) のとき
• \(S_y \bmod N = 0\) かつ \(G_y \bmod N = 0\) かつ \(\lfloor \frac{S_x}{B} \rfloor \neq \lfloor \frac{G_x}{B} \rfloor\) のとき

逆に、上記を満たさないのは以下のような場合です。

• \(S_x \bmod N = 0\) かつ \(G_x \bmod N = 0\) かつ \(\lfloor \frac{S_y}{B} \rfloor = \lfloor \frac{G_y}{B} \rfloor\) のとき
• \(S_y \bmod N = 0\) かつ \(G_y \bmod N = 0\) かつ \(\lfloor \frac{S_x}{B} \rfloor = \lfloor \frac{G_x}{B} \rfloor\) のとき

以下、\(S_x \bmod N = 0\) かつ \(G_x \bmod N = 0\) かつ \(\lfloor \frac{S_y}{B} \rfloor = \lfloor \frac{G_y}{B} \rfloor\) のときを解くこととします。

この場合は、ずっと大通りを使い移動する方法と、大通り以外を使う方法を両方試せばよいです。図だとそれぞれ青と赤の部分です。

よりこの問題を \(\mathrm{O}(T)\) で解くことができました。