現在のマスが白く塗られていて他の白く塗られたマスに隣接しているとき、そのマスに移動し戻ってくることで \(2\) 回の移動を消費することができます。

以下 \(K\) の値によって場合分けをおこないます。

\(K = 2\) のとき

W と B が隣接している箇所があれば Yes 、そうでなければどのように開始地点を選んでも移動できないので No です。

\(K\) が \(3\) 以上の偶数のとき

W と B に同時に隣接しているような W が存在するとき Yes 、そうでなければ No です。これは条件を満たさないと仮定したとき、白く塗られたマスに \(2\) 回以上連続で移動できないことから示すことができます。

\(K\) が \(3\) 以上の奇数のとき

ある B と異なる B のペアであって、 W を \(2\) 以上の偶数かつ \(K-1\) 以下だけ通って一方からもう一方へ移動できるものが存在するとき Yes 、そうでなければ No です。これは各マスについてそのマスにいるときの移動回数の偶奇が開始地点のみによって決まることから示すことができます。

この判定は多始点BFSをおこなうことで計算量 \(O(HW)\) で求めることができます。 B が隣り合うケースは条件を満たさないので、注意が必要です。

以上の場合分けによって、すべてのケースで計算量 \(O(HW)\) で正しい答えを得ることができます。