← 返回题目列表

AtCoder · bcu30_2018_b

B. 泉水

中文机器翻译题面 查看原题

配点 : 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.