?藍橋OJ 178全球變暖

?

思路:

將每一座島嶼用一個顏色scc代替,?用dx[]和dy[]判斷他的上下左右是否需要標記顏色,如果已經標記過顏色或者是海洋就跳過.后面的淹沒,實際上就是哪個塊上下左右有陸地,那么就不會被淹沒,我用一個tag標記,如果上下左右一旦有海洋,tag就變為false.如果tag為true的話,就用一個vis數組判斷是否為同一塊島嶼,如果島嶼前面沒有出現過就ans++,此ans代表沒有被完全淹沒的島嶼,題目問完全淹沒的島嶼有多少,即scc-ans為答案

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
int n, col[N][N], ans, scc;
bool vis[N*N];
char a[N][N];int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};void dfs(int x, int y)
{col[x][y] = scc;for (int k = 0; k < 4; k++){int nx = x + dx[k],ny = y + dy[k];if (col[nx][ny] || a[nx][ny] == '.') continue;dfs(nx,ny);}
}
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 (col[i][j] || a[i][j] == '.') continue;scc++;dfs(i,j);}}//淹沒后for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){bool tag = true;for (int k = 0; k < 4; k++){int x = i + dx[k],y = j + dy[k];if (a[x][y] == '.') tag = false;}if (tag){if (!vis[col[i][j]]) ans++;vis[col[i][j]] = true;}}}cout << scc - ans << '\n';return 0;
}