202. 水洼计数 Lake Counting（挑战程序设计竞赛）

本文主要是介绍202. 水洼计数 Lake Counting（挑战程序设计竞赛），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

地址 https://www.papamelon.com/problem/202

解答
很好的BFS模板题， 也可以尝试DFS。
遍历 每个点 如果是水坑就将其作为起点开始BFS搜索，同一批次搜索的点就是同一个坑。 搜索过的点做上标记，避免重复搜索。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int N = 110;
char arr[N][N];

int n, m;

int addx[] = { 1,-1,1,-1,-1,1,0,0 };
int addy[] = { 0,0,1,-1,1,-1,-1,1 };

void dfs(int x, int y) {
	arr[x][y] = '.';

	for (int i = 0; i < 8; i++) {
		int newx = x + addx[i];
		int newy = y + addy[i];

		if (x >= 0 && x < n && y >= 0 && y < m && arr[newx][newy] == 'W') {
			dfs(newx,newy);
		}
	}

}


int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 'W') {
				ans++; dfs(i,j);
			}
		}
	}
	cout << ans << endl;

	return 0;
}

我的视频题解空间

这篇关于202. 水洼计数 Lake Counting（挑战程序设计竞赛）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！