きままにものづくり

日々の気付いたことなんかを書いてます。

SRM655Div1Easy

問題

サイズX、Yの二次元配列が与えられる。各要素はWかBである。同じサイズの全ての要素がWの二次元配列から以下の操作を行い、与えられた配列にすることができるかを判定せよ。
操作は二次元配列と共に与えられるkを用いて行う。サイズkの正方形を二次元配列内から選択し、すべての要素をWかBにとりかえる。

解法

サイズkのすべてが同じ要素である正方形を見つける。この要素はWでもBであっても最後にまとめて変更することができる要素である。この要素を?で置き換える。W,Bのどちらかと?を保持する正方形を探索し、?に置換する。この処理を更新がなくなるまで行う。すべての要素が?になっている場合は、与えられた配列にすることができる。

計算量

 O((XYk)^2)

コード

広告を非表示にする