問題

$H * W$ の $2$ 次元グリッドが与えられる。各 $a_{ij}$ には $1\leq a_{ij} \leq 9$ のある数が書かれている。以下の操作を繰り返すことで、グリッド上にある数字で偶数のマスの数を最大化するような構築手順を求めよ。

操作
まだ選んでいないマスを $1$ つ選び、隣接 $4$ マスのいずれかのマスに数 $1$ を移す。

考え方

(i)構築したとき最終的な盤面はどのような状態になるか？
すべてのマスの数の合計が偶数の場合は、すべてのマスを偶数マスにできる。合計が奇数の場合は、 $1$ つの奇数のマスが残る。という状態になる。

奇数のマスについて、マスの数を別のマスに移すことで損はしない。

(ii)構築手順
各行について $a_{ij}$ が奇数の場合は、隣の $a_{i(j+1)}$ に数を1つ移すことで $a_{ij}$ を偶数にすることができる。よって盤面を以下のようにたどって、上記の手順を実施すれば良い。

→ → → → → ↓
→ → → → → ↓
→ → → → → ↓
→ → → → → ☆

合計が奇数の場合は☆のマスが奇数になる。

本番中に考えていたこと

1.制約が 500 * 500 だから全探索でしょ
2.適当に偶数のマスは周囲のマスから奇数のマスから数を集める、奇数のマスは奇数のマスに数を配ればいいのでは？
3.WA

さすがに考察が雑でしたね・・・。終盤で適当にサンプルを自分でつくって考えていて、奇数が離れている場合にうまくいかないことがわかりました。本番だと実装バグばかり疑って、どうしても考察が間違っているのに気づけないのでなんとかしたい・・・。