題解 CF948A 【Protect Sheep】

題目連結

額。。這道題亮點在：

$you$ $do$ $not$ $need$ $to$ $minimize$ $their$ $number.$

是以說嘛。。。

直接判斷狼的四周有沒有緊挨着的羊,沒有的話，就直接空地全填狗輸出。

有的話就無解。之後就沒了。。。很暴力。。。

不過如果你問怎麼做才能保證狗最少的話。。。。

貌似是網絡流。

反正我不會。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
char map[510][510];
int r,c;
int main()
{
    scanf("%d%d",&r,&c);
    for(int i=1;i<=r;i++)
      for(int j=1;j<=c;j++)
      cin>>map[i][j];//輸入

    for(int i=1;i<=r;i++)
      for(int j=1;j<=c;j++)
      {
          if(map[i][j]=='S')
          {
              if(map[i-1][j]=='W'||map[i][j-1]=='W'||map[i+1][j]=='W'||map[i][j+1]=='W')//判斷
            {
                printf("No");
                return 0;
            }
        }
      }
      printf("Yes\n");
    for(int i=1;i<=r;i++,puts(""))
      for(int j=1;j<=c;j++)
      {
          if(map[i][j]=='.') printf("D");//如果是空地，則全變成狗。
        else printf("%c",map[i][j]);//輸出。
      }
      return 0;//程式拜拜。
    
}
/*
6 6
..S...
..S.W.
.S....
..W...
...W..
......

DDSDDD
DDSDWD
DSDDDD
DDWDDD
DDDWDD

1 2
SW


*/