鲍勃是一名农民。他有一个大牧场,有很多羊。最近,他因为狼的袭击而失去了一些。因此,他决定安置一些牧羊犬,以保护他所有的羊。
牧场是一个由 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) 处的羊是安全的,因为狼不能沿对角线移动。
在第二个示例中,没有空位来放置可以看守孤独羊的狗。
在第三个例子中,没有狼,所以任务很简单。我们在中间放了一只狗来观察草地的宁静,但即使没有它,解决方案也是正确的。