Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 246 E問題 Bishop 2

AtCoder ABC ABC246 E問題 500 pts

問題

提出解答

問題の概要

$N \times N$ のチェス盤がある. $S_i[j]={\tt .}$ ならば, マス $(i,j)$ に白のポーンがなく, $S_i[j]={\tt \#}$ ならば, マス $(i,j)$ に白のポーンが置かれている. このポーンは動かせない.

マス $(A_x, A_y)$ に白のビジョップが置かれているとき, 合法的な動きでマス $(B_x, B_y)$ に移動できるか? できる場合はその移動の最小回数を求めよ.

制約

$2 \leq N \leq 1500$
$1 \leq A_x, A_y \leq N$
$1 \leq B_x, B_y \leq N$
$(A_x, A_y) \neq (B_x, B_y)$
$S$ は $'{\tt .}', '{\tt \#}'$ からなる文字列
$(A_x, A_y),(B_x, B_y)$ にポーンはない.

解法

愚直な BFS で求めようとした場合, 方向の情報が込められず, その結果, 一度見たマスを飛び越えるような場合において正しく計算できない.

そこで, 方向の情報を込めることにする.

重み付き有向グラフ $D=(V,A,C)$ を

$V:=[\![N]\!] \times [\![N]\!] \times \{0,1\}$
$A:=\{\overrightarrow{(i,j,d)(i',j',d)} ~;~ |i-i'|=1, |j-j'|=1, d \in \{0,1\} \} \coprod \{\overrightarrow{(i,j,d)(i',j',1-d)} ~;~ |i-i'|=1, |j-j'|=1, d \in \{0,1\} \}$
$C: A \to \mathbb{R}; \overrightarrow{(i,j,d)(i',j',d')} \mapsto [d \neq d']$

とする. このグラフのイメージは $d$ が移動の方向 *1 を表す. また, $C$ のコストはこの問題ではできるならば同一方向に無限に移動できる. このことから, 操作の回数は方向転換の回数 (+1) である.

この $D$ において, 答えは

$\displaystyle \min_{d,d' \in \{0, 1\} } \operatorname{dist}_D ( (A_x, A_y, d), (B_x, B_y, d'))$

である.

これは $C(A) \subset \{0,1\}$ であることから, 0-1 BFS で求めることができ, 時間計算量 $O(N^2)$ で求めることができる.

*1:例えば, $d=0$ が右斜め下方向, $d=1$ が右斜め上方向