画像のグラデーション
高さが
h、幅が w の白黒画像に対して、グラデーションフィルターを適用するよう求められています。つまり、黒と白の画素ではなく、最も近い白画素との距離に基づいて段階的な値を持つように変換します。初期状態では、黒画素はすべて 1 に、白画素はすべて 0 に設定されています。変換後の画像では、黒画素に「最も近い白画素からの距離」が値として設定されます。距離は上下左右の方向にのみ移動するとき、あるセルから別のセルまでに必要なステップ数で測ります。
入力
最初の行に 2 つの整数
h と w (1 ≤ h, w ≤ 500) が与えられます。続く
h 行には、画像の初期状態を表す w 個の数字が書かれています。出力
変換後の画像を出力してください。
例
入力 | 出力 |
3 4
1 1 1 0
1 1 0 0
1 0 0 1 | 3 2 1 0
2 1 0 0
1 0 0 1 |
ヒント
1 つのセルからではなく、複数の始点から同時に BFS (幅優先探索) を行うこともできます。
文献では、これをマルチソース BFS と呼びます。
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 2.5 MB