Bài A - Codeforces Round #470 (Div.2)

Bài A:
Đề bài: Bob là một người nông dân. Anh ta có một đồng có (pasture) lớn với nhiều cừu. Gần đây, anh ta bị mất một số con do sói tấn công. Vì vậy, anh ấy quyết định sắp đặt một vài con chó thiện chiến để chúng có thể bảo vệ loài cừu.
  Cánh đồng là hình chữ nhật có kích thước RxC. Mỗi ô là trống hoặc là cừu hoặc là soái hoặc là chó. Cừu và chó luôn luôn ở chung một chỗ, nhưng sói có thể đi lang thang (roam) tự do xung quanh đồng cỏ, bằng việc lặp lại việc di chuyển: lên, xuống, trái, phải các ô lân cận. Khi con sói đi vào một ô có 1 con cừu, nó sẽ ăn nó. Tuy nhiên, không có con soi nào có thể đi vào ô có con chó.
  Ban đầu không có con chó nào. Hãy đặt các con chó vào đồng cỏ bằng một cách nào đó sao cho không có sói nào có thể ăn được cừu, hoặc xác định liệu rằng điều này là không thể.
Chú ý rằng bởi vì bạn có nhiều chó, bạn không cần phải tối thiểu con số này.
Đầu vào:
+ Dòng đầu tiên chứa hai số nguyên R(1<=R<=500) và C(1<=C<=500), kí hiệu số hàng và cột lần lượt.
+ Có R dòng, mỗi dòng là 1 xâu chứa chính xác C kí tự, là 1 hàng của đồng cỏ. Ở đây, 's' có nghĩa là cừu, 'w' có nghĩa là sói và '.' có nghĩa là rỗng.
Đầu ra:
+ Nếu không thể bảo vệ được cừu, in ra một dòng :No.
+ Ngược lại, in ra Yes. Sau đó in R dòng, thể hiện đồng cỏ sau khi đặt các chú chó vào. Một lần nữa, 'S' có nghĩa là cừu, 'W' có nghĩa là sói, 'D' có nghĩa là chó và '.' có nghĩa là không gian trống. Bạn được không được phép di chuyển, loại bỏ hay thêm một con cừu hay sói nào.
Nếu có nhiều đáp án, in ra bất kỳ. Bạn không nhất thiết phải dùng số chó tối thiểu.
Ví dụ:
Đầu vào:
6 6
..S...
..S.W.
.S....
..W...
...W..
......
Đầu ra:
Yes
..SD..
..SDW.
.SD...
.DW...
DD.W..
......
/**/
Đầu vào:
1 2
SW
Đầu ra:
No
/***/
Đầu vào:
5 5
.S...
...S.
S....
...S.
.S...
Đầu ra:
Yes
.S...
...S.
S.D..
...S.
.S...
/**/
Chú ý rằng: Ở ví dụ đầu tiên, chúng ta có thể chia đồng cỏ thành hai phần, một phần chứa sói, một phần chứa cừu. Chú ý rằng cừu tại (2,1) thì an toàn, bởi vì sói không thể di chuyển chéo.
Ở ví dụ 2, không có dấu chấm nào đề đặt chó vào bảo vệ (guard) đàn cừu cô độc.
Ở ví dụ 3, không có con sói nào, vì vậy nhiệm vụ rất dễ. Chúng ta đặt 1 con chó ở trung tâm để quan sát cảnh bình yên của đồng cỏ (meadow), nhưng câu trả lời cũng đúng thậm chí không có anh ta.
Hướng dẫn:
Giả sử rằng có một con sói và một con cừu kề nhau. Rõ ràng chúng ta thấy rằng, đáp án là NO
Ngược lại, câu trả lời luôn luôn là Yes. Cách đơn giản để bảo vệ các loài cừu đó là đặt tất cả các con chó vào các ô trống. Thì không có con sói nào có thể di chuyển và tất cả con cừu được bảo vệ và hạnh phúc.
Lời giải:

#include<cstdio>
int n,m;
char s[505][505];
int main(){
 scanf("%d%d",&n,&m);
 for (int i=1;i<=n;i++){
  int j=1;
  char c=getchar();
  while (c!='S'&&c!='.'&&c!='W') c=getchar();
  while (c=='S'||c=='.'||c=='W') s[i][j++]=c,c=getchar();
 }
 for (int i=1;i<=n;i++)
  for (int j=1;j<=m;j++)if (s[i][j]=='.')s[i][j]='D';
  else if (s[i][j]=='S'&&(s[i-1][j]=='W'||s[i+1][j]=='W'||s[i][j-1]=='W'||s[i][j+1]=='W')){printf("No\n");return 0;}
 printf("Yes\n");
 for (int i=1;i<=n;i++)printf("%s\n",s[i]+1);
}