CF116B Little Pigs and Wolves 题解

Content

有一张 \(n\times m\) 的地图，其中，\(\texttt{P}\) 代表小猪，\(\texttt{W}\) 代表狼。如果狼的上下左右有一头以上的小猪，那么它会吃掉其中相邻的任意一头小猪（此过程不再重复）。求有多少头小猪会被狼吃掉。

数据范围：\(1\leqslant n,m\leqslant 10\)。

Solution

如果 \(n,m\) 的范围很大，那么 @123456zmy 巨佬的 \(\texttt{Dinic}\) 算法无疑是一个绝佳的选择。

然而，这题目中 \(n,m\) 的范围实在小到可怜，我们为什么不直接暴力模拟呢？如果仔细看题的话不难发现，这道题目实质上就是想问你有多少匹狼能够吃到小猪。所以，我们可以记录下来每一匹狼的位置，然后遍历每个狼的上下左右是否会有小猪，有的话那么这匹狼就能够吃到一头小猪，记录答案之后输出就好了。

Code

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <iostream>

using namespace std;

const int dx[4] = {0, 0, -1, 1};

const int dy[4] = {-1, 1, 0, 0};

int n, m, xwolf[107], ywolf[107], cnt, ans;

char s[17][17];

int main() {

	scanf("%d%d", &n, &m);

	for(int i = 1; i <= n; ++i) {

		scanf("%s", s[i] + 1);

		for(int j = 1; j <= m; ++j)

			if(s[i][j] == 'W')	xwolf[++cnt] = i, ywolf[cnt] = j;

	}

	for(int i = 1; i <= cnt; ++i)

		for(int j = 0; j < 4; ++j)

			if(s[xwolf[i] + dx[j]][ywolf[i] + dy[j]] == 'P') {

				ans++;

				break;

			}

	printf("%d", ans);

	return 0;

}

巴特西

CF116B Little Pigs and Wolves 题解

Content

Solution

Code

最新文章

热门文章