-
-
考えたこと
- 高々10^6頂点で、最悪10^3回処理をする
- 毎回全頂点をチェックすると10^9で間に合わないがそんなことはしない
- 幅優先探索すれば10^6オーダーで処理が終わるのでOK
-
- 無意識に問題を書き換えてた
- 「すべての白マスの内、黒マスに隣接しているものを黒にする」は「すべての黒マスについて、隣接マスに白マスがあるなら、それを黒にする」と同じ
- 黒マスに隣接している白マスを黒にする
- 確かにこの言い換えに気づかなければ悩んだかもな
- 後者では一度処理した黒マスは周囲に白マスがなくなるので二度と処理する必要がない、これがオーダーが減る原理
