每日一题洛谷P8662 [蓝桥杯 2018 省 AB] 全球变暖c++

P8662 [蓝桥杯 2018 省 AB] 全球变暖 - 洛谷 (luogu.com.cn)

DFS

#include<iostream>
using namespace std;
int n, res;
char a[1005][1005]; bool vis[1005][1005];
bool flag;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
void dfs(int x, int y) {
	vis[x][y] = true;
	bool safe = false;
	for (int i = 0; i < 4; i++) {
		int xx = x + dx[i];
		int yy = y + dy[i];
		if (xx<1 || yy<1 || xx>n || yy>n || a[xx][yy] == '.') {
			safe = true;
			break;
		}
	}
	if (!safe)flag = true;
	for (int i = 0; i < 4; i++) {
		int xx = x + dx[i];
		int yy = y + dy[i];
		if (xx >= 1 && yy >= 1 && x <= n && yy <= n && a[xx][yy] == '#' && !vis[xx][yy]) {
			dfs(xx, yy);
		}
	}
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)cin >> a[i][j];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (a[i][j] == '#' && !vis[i][j]) {
				flag = false;
				vis[i][j] = true;
				dfs(i, j);
				if (!flag)res++;
			}
			flag = false;
		}
	}
	cout << res;
	return 0;
}

BFS

#include<iostream>
using namespace std;
#include<queue>
int n, res;
char a[1001][1001]; bool vis[1001][1001];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
bool bfs(int x, int y) {
	vis[x][y] = true;
	queue<pair<int, int>> q;
	bool flag = false;
	q.push({ x,y });
	while (!q.empty()) {
		pair<int, int> t = q.front();
		q.pop();
		bool safe = false;
		for (int i = 0; i < 4; i++) {
			int xx = t.first + dx[i];
			int yy = t.second + dy[i];
			if (xx<1 || yy<1 || xx>n || yy>n || a[xx][yy] == '.') {
				safe = true;
				break;
			}
		}
		if (!safe)flag = true;
		for (int i = 0; i < 4; i++) {
			int xx = t.first + dx[i];
			int yy = t.second + dy[i];
			if (xx >= 1 && yy >= 1 && xx <= n && yy <= n && a[xx][yy] == '#' && !vis[xx][yy]) {
				vis[xx][yy] = true;
				q.push({ xx,yy });
			}
		}
	}
	return !flag;
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)cin >> a[i][j];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (a[i][j] == '#' && !vis[i][j]) {
				if (bfs(i, j))res++;
			}
		}
	}
	cout << res;
	return 0;
}