59 lines
1.4 KiB
C++
59 lines
1.4 KiB
C++
// lanqiao 178 全球变暖
|
||
#include<bits/stdc++.h>
|
||
using namespace std;
|
||
const int N = 1e3 + 10;
|
||
char mp[N][N];
|
||
int n, scc, col[N][N];
|
||
bool vis[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 i = 0; i < 4; i++){
|
||
int nx = x + dx[i], ny = y + dy[i];
|
||
if( col[nx][ny] || mp[nx][ny] == '.') continue; // 不需要判断nx, ny是否在地图里面，因为地图边缘都是海洋
|
||
dfs(nx ,ny);
|
||
}
|
||
}
|
||
|
||
int main(){
|
||
ios::sync_with_stdio, cin.tie(0), cout.tie(0);
|
||
cin >> n;
|
||
for(int i = 1; i <= n; i++) cin >> mp[i] + 1;
|
||
for(int i = 1; i <= n; i++){
|
||
for(int j = 1; j <= n; j++){
|
||
if(col[i][j] || mp[i][j] == '.') continue;
|
||
scc++; // scc表示当前颜色编号
|
||
dfs(i, j);
|
||
}
|
||
}
|
||
int ans = 0;
|
||
for(int i = 1; i <= n; i++){
|
||
for(int j = 1; j <= n; j++){
|
||
if(mp[i][j] == '.') continue;
|
||
bool tag = true;
|
||
for(int k = 0; k < 4; k++){
|
||
int x = i + dx[k], y = j + dy[k];
|
||
if(mp[x][y] == '.') tag = false;
|
||
}
|
||
if(tag){
|
||
if(!vis[col[i][j]]) ans++;
|
||
vis[col[i][j]] = true;
|
||
}
|
||
}
|
||
}
|
||
cout << scc - ans << '\n';
|
||
return 0;
|
||
}
|
||
/* test samples
|
||
7
|
||
.......
|
||
.##....
|
||
.##....
|
||
....##.
|
||
..####.
|
||
...###.
|
||
.......
|
||
*/ |