Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 100 点
問題文
南北方向に H 個、東西方向に W 個に区切られた H \times W 個の区画からなる公園があり、北から i 番目、西から j 番目の区画は区画 (i,j) です。
区画 (i,j) の標高は A_{i,j} であり、全ての区画の標高は異なります。
区画 (s_x,s_y) で湧き水が出ました。
水は東西南北のいずれかの方向で隣り合う、今の区画より標高の低い区画(ただし公園の内部にあるものに限る)のうち、最も標高が低い区画のみに流れます。ただし、これらの区画の標高が全て今の区画より高い場合は、今の区画ににとどまり、周囲の区画に流れ出しません。
区画 (s_x,s_y) を含めた水が流れる区画を W
、そうでない区画を .
と表して出力してください。
制約
- 1 \leq H,W \leq 500
- 1 \leq s_x \leq H
- 1 \leq s_y \leq W
- 1 \leq A_{i,j} \leq H \times W
- A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))
入力
入力は以下の形式で標準入力から与えられる。
H W s_x s_y A_{1,1} ... A_{1,W} : A_{H,1} ... A_{H,W}
出力
i 番目の文字列の j 番目の文字が、区画 (i,j) に水が流れるなら W
、そうでないなら .
となるように、長さ W の文字列を H 個出力せよ。
入力例 1
3 3 2 2 5 6 7 3 9 2 4 8 1
出力例 1
... .WW ..W
-
区画 (2,2) で湧き水が出ました。
-
区画 (2,2) と隣り合い、かつ区画 (2,2) より標高の低い区画のうち、最も標高が低い区画は区画 (2,3) なので、水は区画 (2,3) に流れます。
-
区画 (2,3) と隣り合い、かつ区画 (2,3) より標高の低い区画のうち、最も標高が低い区画は区画 (3,3) なので、水は区画 (3,3) に流れます。
-
区画 (3,3) と隣り合う区画の標高は全て区画 (3,3) の標高より高いため、水は区画 (3,3) にとどまります。
入力例 2
3 3 2 2 3 8 2 6 5 7 1 9 4
出力例 2
... .W. ...
水が区画 (s_x,s_y) にとどまる場合に注意してください。
入力例 3
4 4 2 1 16 10 9 7 13 11 12 6 14 15 4 5 1 2 3 8
出力例 3
.WWW WW.W ..WW WWW.