題目描述

全球變暖 - 藍(lán)橋云課 (lanqiao.cn)

題目分析?

果然有關(guān)連通塊類的問題使用dfs都較為好寫~~

我們可以通過判斷連通塊的代碼來加上部分條件算出被完全淹沒的島嶼個數(shù)

在島嶼中如果有為"#"的a[i][j]上下左右全部是"#"則說明此島嶼一定不會被完全淹沒，但如果此連通塊全部被遍歷后發(fā)現(xiàn)沒有這種情況則這個島嶼一定會被完全淹沒，這時我們才看做它是真正我們要求的連通塊，我們將其算入答案

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 2e3 + 10;
int n, cnt, ans;
char a[N][N];
bool st[N][N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
void dfs(int x, int y)
{st[x][y] = 1;int o = 0;for(int i = 0; i < 4; i ++){int aa = x + dx[i];int bb = y + dy[i];if(a[aa][bb] == '#')o ++;}if(o == 4)cnt ++;for(int i = 0; i < 4; i ++){int aa = x + dx[i];int bb = y + dy[i];if(a[aa][bb] == '#' && !st[aa][bb])dfs(aa, bb);}
}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(!st[i][j] && a[i][j] == '#'){cnt = 0;dfs(i, j);if(cnt == 0)ans ++;}	}}cout << ans;return 0;
}