每日一题洛谷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;
}