当前位置: 代码迷 >> 综合 >> Codeforces Round #470 (Div. 2) A Protect Sheep (基础)输入输出的警示、边界处理
  详细解决方案

Codeforces Round #470 (Div. 2) A Protect Sheep (基础)输入输出的警示、边界处理

热度:32   发布时间:2023-12-23 12:22:46.0

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.

Input

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.

Output

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.

Examples
input
Copy
6 6
..S...
..S.W.
.S....
..W...
...W..
......
output
Yes
..SD..
..SDW.
.SD...
.DW...
DD.W..
......
input
Copy
1 2
SW
output
No
input
Copy
5 5
.S...
...S.
S....
...S.
.S...
output
Yes
.S...
...S.
S.D..
...S.
.S...
Note

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.

题意:输入如题。。在 '.' 中添加 'D' 使得W不能碰到S

题解:直接先判断S旁边有没有W,如果有就NO,然后把所有的点变成D即可。。

这题坑的是输入。。。这场一直在刚输入,发现自己对于最基础的字符串输入掌握的很差劲啊

这题不能这样读数据:

//不能这样!
scanf("%d %d", &n, &m);for (int i=0;i<n;i++)for (int j=0;j<m;j++)scanf("%c",&a[i][j]);
原因:读入n、m后,要敲回车完成m的读入,于是回车'\n'便被读入到a[0][0]中了!同样,在二维数组的每一行末输出,都导致了一个\n被读进去
于是这题无限GG

  参考别人的代码,总结出了几种读入的办法:

scanf("%d %d", &n, &m);for (int i=0;i<n;i++)for (int j=0;j<m;j++)scanf(" %c",&a[i][j]);//注意这里有空格
char a[maxn][maxn];for (int i=0;i<n;i++)scanf("%s",a[i]);//这里可以没有空格(加空格也阔以),同时读入字符串,前面没有取地址符//因为题目给的输入方式,一行中的字符之间没有空格,所以可以以字符串的形式读取
//如果输入形式为 S S W W . . W这样的话,scanf遇到空格会停止读入,cin也是

scanf读入空格的方法:scanf("%[^\n]",a[i]);

其中^\n代表以\n为结束符

当然也可以cin.getline(a[i], maxn);

以下是本题的几个完整代码,注意此类题查找相邻位置以及处理边界的方法。

还有可以不用看到'.'就更改为D,可以在确定Yes之后遍历数组,看到'.'就打印D,妙哉。

#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin                    \ios_base::sync_with_stdio(0); \cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;
const int N = 505;
char s[N][N];
bool vis[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};//←←重点在这里
int n, m;
void dfs(int x, int y, const char& c)
{if (x < 0 || y < 0 || x >= n || y >= m) return;//边界处理(这题因为可以直接全D,所以不一定要dfs)if (vis[x][y] || s[x][y] == '.') return;if (s[x][y] != c){cout << "No";exit(0);}vis[x][y] = 1;for (int i = 0; i < 4; i++) dfs(x + dx[i], y + dy[i], c);
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endifcin >> n >> m;for (int i = 0; i < n; i++)for (int j = 0; j < m; j++) cin >> s[i][j];for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)if (s[i][j] != '.' && !vis[i][j])dfs(i, j, s[i][j]);cout << "Yes" << endl;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (s[i][j] == '.')cout << "D";elsecout << s[i][j];}cout << endl;}return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};const int N=510;
char s[N][N];int main() {int n,m; scanf("%d%d",&n,&m);for (int i=0;i!=n;++i) scanf("%s",s[i]);int flag=0;for (int i=0;i!=n;++i) {for (int j=0;j!=m;++j) {for (int k=0;k!=4;++k) {int px=i+dx[k], py=j+dy[k];if (px>=0 && px<n && py>=0 && py<m && s[i][j]=='W' && s[px][py]=='S') flag=1;}}}if (flag) {printf("No\n");} else {printf("Yes\n");for (int i=0;i!=n;++i)for (int j=0;j!=m;++j)if (s[i][j]=='.') s[i][j] = 'D';for (int i=0;i!=n;++i) printf("%s\n",s[i]);}
}

  相关解决方案