2019 GDUT Winter Personal Training Contest I (Div. 2) A. Protect Sheep 题目见 ：
http://codeforces.com/group/NVaJtLaLjS/contest/236426/problem/A
题目大意： 一个长宽分别为R,C(<=500)的长方形，里面有字符 s ——羊，w ——狼，. ——空地，你可以在空地放上任意数量狗，使得狼上下左右走无法到达羊吗？打出一种方案。
思路： 【2019 GDUT Winter Personal Training Contest I (Div. 2) A. Protect Sheep】对于一种成功的方案，用狼作为起点进行dfs，判断能否到达羊。
一次优化： 题目没限制狗的数量，那就不妨把所有空地全部放上狗，这样狼就只能被堵在原地，这样只需判断狼的四周有没有羊即可。
实现：
#include
#includeintmain()
{int n,r,c,k,t,i,j,p;
char s[550][550];
scanf("%d %d",&r,&c);
for (i=1;
i<=r;
i++)
{
scanf("%s",&s[i]);
for (j=c;
j>=1;
j--) s[i][j]=s[i][j-1];
}
for (i=0;
i<=r+1;
i++)
{
s[i][0]='.';
s[i][c+1]='.';
}for (j=0;
j<=c+1;
j++)
{
s[0][j]='.';
s[r+1][j]='.';
}
p=0;
for (i=1;
i<=r;
i++)
for (j=1;
j<=c;
j++)
if (s[i][j]=='S'&&(s[i][j-1]=='W'||s[i][j+1]=='W'||s[i-1][j]=='W'||s[i+1][j]=='W'))
p=1;
if (p==1) printf("No\n");
else
{
printf("Yes\n");
for (i=1;
i<=r;
i++)
{
for (j=1;
j<=c;
j++)
if (s[i][j]=='.') printf("D");
else printf("%c",s[i][j]);
printf("\n");
}
}
return 0;
}
推荐阅读
- 题解|【HNOI2017】大佬-dalao
- 2019 GDUT Rating Contest #II 这是群题解，七篇！！！
- # 2019 GDUT Rating Contest #I H. Mixing Milk
- # 2019 GDUT Rating Contest #I A. The Bucket List
- # 2019 GDUT Rating Contest #I G. Back and Forth
- 2019 GDUT Winter Personal Training Contest III (Div. 2) A题 QAQ 题解
- 题解|题解 | K-ary Heap-2019牛客暑期多校训练营第六场F题
- ACM|[dsu] codeforces 375D. Tree and Queries
- 题解|[BZOJ3817] Sum