DFS

#include <bits/stdc++.h>
using namespace std;
int fx[4][2]={-1,0,0,-1,1,0,0,1};
int n;
char a[1100][1100];
char s[1100][1100];
int d[1100][1100];
int c[10000000][2];
int qw[100000];
int t;
void dfs(int x, int y, int xxx) {
d[x][y] = xxx;
c[t * 1000 + qw[xxx]][0] = x;
c[t * 1000 + qw[xxx]][1] = y;
qw[xxx];
for(int i = 0; i < 4; i) {
int xx = x + fx[i][0];
int yy = y + fx[i][1];
if(xx >= 1 && xx <= n && yy >= 1 && yy <= n && a[xx][yy] == '#' && d[xx][yy] == -1) {
dfs(xx, yy, xxx);
}
}
}
int main() {
cin >> n;
memset(d, -1, sizeof(d));
memset(qw, 0, sizeof(qw));
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
cin >> a[i][j];
s[i][j] = a[i][j];
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(a[i][j] == '#' && d[i][j] == -1) {
dfs(i, j, t);
t++;
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(a[i][j] == '#') {
int fg = 0;
for(int k = 0; k < 4; k++) {
int xx = i + fx[k][0];
int yy = j + fx[k][1];
if(xx < 1 || xx > n || yy < 1 || yy > n || a[xx][yy] == '.') {
fg = 1;
break;
}
}
if(fg) s[i][j] = '.';
}
}
}
int y = 0;
for(int i = 0; i < t; i++) {
int gh = 1;
for(int j = 0; j < qw[i]; j++) {
int x = c[i * 1000 + j][0];
int y = c[i * 1000 + j][1];
if(s[x][y] == '#') {
gh = 0;
break;
}
}
if(gh!=0) y++;
}
cout << y;
return 0;
}