Huge Huge Cat

解説

概要

この問題は、以下の 3 つのステップ を順に判定することで、$O(N^2)$ で解くことができます。

1. 偶奇性のチェック
2. 0-1 BFSによる最小またぎ回数の計算
3. 往復の判定

---

1. 偶奇性の考察

高橋くんが「毛の色をまたぐ移動」を $1$ 回行うたびに、現在地にある毛の色は必ず $0 \to 1$ または $1 \to 0$ と反転します。一方、同じ色の毛へ移動しても色は変わりません。

このことから、色をまたぐ移動の回数と、毛の色の関係には以下の性質があります。

• 移動回数が 偶数 回のとき：現在地の毛の色は、始点と同じ色
• 移動回数が 奇数 回のとき：現在地の毛の色は、始点と異なる色

したがって、始点 $(0, 0)$ の毛の色を $C_{0, 0}$、終点 $(x, y)$ の毛の色を $C_{x, y}$ とすると、

• $C_{0, 0} = C_{x, y}$ のとき：$K$ は 偶数 でなければならない
• $C_{0, 0} \neq C_{x, y}$ のとき：$K$ は 奇数 でなければならない

この偶奇が一致していない場合は、どのように移動しても目的地にちょうど $K$ 回で到達することは不可能なため、即座に No と判定できます。

---

2. 0-1 BFSによる最小またぎ回数の計算

目的地 $(x, y)$ に到達するために、「毛の色をまたぐ移動」を最低何回行う必要があるか を考えます。

これは、グリッド上の移動コストを以下のように定義することで、重み付きグラフの最短経路問題に言い換えることができます。

• 同じ色の毛への移動：コスト $0$
• 異なる色の毛への移動：コスト $1$

移動コストが $0$ と $1$ のみであるため、0-1 BFS を用いることで、始点 $(0, 0)$ からすべてのマスへの最小コストを $O(N^2)$ で求めることができます。 0-1BFSについては、以下の解説記事を参照してください。

• 01-BFSのちょっと丁寧な解説（ARMERIA)

こうして求めた $(x, y)$ への最小コスト（最小またぎ回数）を $d$ とします。 もし $K < d$ であれば、どのようなルートを通っても $K$ 回以内で到達できないため No となります。

---

3. 余った回数の処理

パリティが一致しており、$K \ge d$ である場合、差分である $K - d$ は必ず $0$ 以上の偶数（$+0, +2, +4, \dots$）になります。

この余った回数は、異なる色の毛が隣接している場所を $1$ 往復するたびに $+2$ 回ずつ消費 することができます。

盤面に色 $0$ と色 $1$ が両方存在する場合

$N \ge 2$ のグリッドは連結であるため、盤面に色 $0$ と色 $1$ が両方存在すれば、必ずどこかに「色が異なる隣接した $2$ つの毛」が存在します。
その場所を行き来することで回数を $+2$ ずつ増やせるため、必ずちょうど $K$ 回に合わせることができ、判定は Yes となります。

盤面の毛の色がすべて同じ場合

盤面の毛がすべて $0$、またはすべて $1$ の場合、グリッド内に異なる色の隣接が存在しません。 この場合、一度も色を跨ぐことができないため、

• $K = 0$ のときは移動可能なので Yes
• $K > 0$ のときは回数を稼ぐことができず No となります。

---

計算量

• 0-1 BFS による最短経路探索：$O(N^2)$
• 盤面の単色チェックおよびパリティ判定：$O(N^2)$

全体の計算量は $O(N^2)$ であり、制約 $N^2 \le 10^5$ に対して十分高速に動作します。

---

解答例 (C++23)

作者解