← 返回题目列表

Codeforces · 948/A

A. 保护羊

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

鲍勃是一名农民。他有一个大牧场,有很多羊。最近,他因为狼的袭击而失去了一些。因此,他决定安置一些牧羊犬,以保护他所有的羊。

牧场是一个由 R × C 单元格组成的矩形。每个牢房要么是空的,要么是一只羊、一只狼或一只狗。羊和狗总是呆在原地,但狼可以在牧场周围自由漫步,反复向左、向右、向上或向下移动到相邻的单元格。当狼进入有羊的牢房时,它就会吃掉它。然而,狼不能进入有狗的牢房。

最初没有狗。将狗放在牧场上,确保狼无法接近任何羊,或者确定这是不可能的。请注意,由于您有很多狗,因此无需减少它们的数量。

输入

第一行包含两个整数R(1≤R≤500)和C(1≤C≤500),分别表示行数和列数。

以下R行都是由C个字符组成的字符串,代表牧场的一行。这里,“S”代表羊,“W”代表狼,“.”代表羊。一个空单元格。

输出

如果无法保护所有羊,则输出一行“否”。

否则,输出一行包含“Yes”的单词。然后打印R线,代表放置狗后的牧场。同样,“S”表示羊,“W”表示狼,“D”表示狗,“.”一个空的空间。您不得移动、移除或添加羊或狼。

如果有多个解决方案,您可以打印其中任何一个。您不必减少狗的数量。

示例

输入 #1

6 6
..S...
..S.W.
.S....
..W...
...W..
......

输出 #1

Yes
..SD..
..SDW.
.SD...
.DW...
DD.W..
......

输入 #2

1 2
SW

输出 #2

No

输入 #3

5 5
.S...
...S.
S....
...S.
.S...

输出 #3

Yes
.S...
...S.
S.D..
...S.
.S...

注意

在第一个示例中,我们可以将牧场分成两半,一半包含狼,一半包含羊。请注意,(2,1) 处的羊是安全的,因为狼不能沿对角线移动。

在第二个示例中,没有空位来放置可以看守孤独羊的狗。

在第三个例子中,没有狼,所以任务很简单。我们在中间放了一只狗来观察草地的宁静,但即使没有它,解决方案也是正确的。