CF948A.Protect Sheep

Bob is a farmer. He has a large pasture with many sheep. Recently, he has lost some of them due to wolf attacks. He thus decided to place some shepherd dogs in such a way that all his sheep are protected.

The pasture is a rectangle consisting of R × C cells. Each cell is either empty, contains a sheep, a wolf or a dog. Sheep and dogs always stay in place, but wolves can roam freely around the pasture, by repeatedly moving to the left, right, up or down to a neighboring cell. When a wolf enters a cell with a sheep, it consumes it. However, no wolf can enter a cell with a dog.

Initially there are no dogs. Place dogs onto the pasture in such a way that no wolf can reach any sheep, or determine that it is impossible. Note that since you have many dogs, you do not need to minimize their number.

鲍勃是一位农民，他拥有一大片牧场，里面养了许多羊。最近，由于狼的袭击，他丢失了一些羊。因此，他决定放置一些牧羊犬，以确保所有羊都得到保护。

牧场是一个由 $R \times C$ 个格子组成的矩形。每个格子要么为空，要么包含一只羊、一只狼或一只狗。羊和狗始终固定在原地不动，而狼可以在牧场内自由移动：它们可以反复向左、向右、向上或向下移动到相邻的格子。当一只狼进入一个含有羊的格子时，它会吃掉这只羊。然而，任何狼都无法进入含有狗的格子。

初始状态下，牧场中没有任何狗。请在牧场上放置若干只狗，使得没有任何一只狼能够到达任意一只羊；或者判断这是不可能的。注意：由于你拥有足够多的狗，因此无需最小化所用狗的数量。

First line contains two integers R (1 ≤ R ≤ 500) and C (1 ≤ C ≤ 500), denoting the number of rows and the numbers of columns respectively.

Each of the following R lines is a string consisting of exactly C characters, representing one row of the pasture. Here, 'S' means a sheep, 'W' a wolf and '.' an empty cell.

第一行包含两个整数 $R$（$1 \leq R \leq 500$）和 $C$（$1 \leq C \leq 500$），分别表示牧场的行数和列数。

接下来的 $R$ 行中，每行是一个长度恰好为 $C$ 的字符串，表示牧场的一行。其中，'S' 表示一只绵羊，'W' 表示一只狼，'.' 表示一个空单元格。

If it is impossible to protect all sheep, output a single line with the word "No".

Otherwise, output a line with the word "Yes". Then print R lines, representing the pasture after placing dogs. Again, 'S' means a sheep, 'W' a wolf, 'D' is a dog and '.' an empty space. You are not allowed to move, remove or add a sheep or a wolf.

If there are multiple solutions, you may print any of them. You don't have to minimize the number of dogs.

如果无法保护所有绵羊，则输出一行单词“No”。

否则，输出一行单词“Yes”。然后输出 R 行，表示放置狗之后的牧场布局。其中，'S' 表示绵羊，'W' 表示狼，'D' 表示狗，'.' 表示空地。你不允许移动、移除或添加任何绵羊或狼。

若存在多种可行解，可输出任意一种。你无需最小化狗的数量。

In the first example, we can split the pasture into two halves, one containing wolves and one containing sheep. Note that the sheep at (2,1) is safe, as wolves cannot move diagonally.

In the second example, there are no empty spots to put dogs that would guard the lone sheep.

In the third example, there are no wolves, so the task is very easy. We put a dog in the center to observe the peacefulness of the meadow, but the solution would be correct even without him.

在第一个例子中，我们可以将牧场分成两半，一半放置狼，另一半放置羊。注意，位于 (2,1) 处的羊是安全的，因为狼不能斜向移动。

在第二个例子中，没有空位可以放置狗来保护那只孤零零的羊。

在第三个例子中，没有狼，因此任务非常简单。我们在中心放置一只狗以观察草场的宁静，但即使不放这只狗，解法也是正确的。