- やるだけbfsはコピペで済ませよう
- 今回の設定では、地図が
##.
#..
...
- のようにドットが空地、#が壁として、空地が連結かを判定する
ll H,W;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = { 0, 1, 0, -1};
bool in_range(ll i, ll j){
if(0<=i && i<H && 0<=j && j<W){
return true;
}else{
return false;
}
}
bool bfs(VS S, PII start){
ll spaces = 0;
for(string s : S){
for(char c : s){
if(c=='.')spaces++;
}
}
ll paint=0;
queue<PII> que;
que.push(start);
S[start.first][start.second]='#'; paint++;
while(!que.empty()){
auto pa = que.front(); que.pop();
rep(i,4){
ll ny = pa.first + dy[i];
ll nx = pa.second + dx[i];
if(!in_range(ny,nx))continue;
if(S[ny][nx]=='.'){
que.push({ny,nx});
S[ny][nx]='#'; paint++;
}
}
}
return spaces==paint;
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
cin>>H>>W;
VS S(H);
rep(i,H)cin>>S[i];
ll cnt=0;
rep(i,H){
rep(j,W){
if(S[i][j]=='.')continue;
S[i][j]='.';
bool connected = bfs(S, {i,j});
S[i][j]='#';
if(connected)cnt++;
}
}
p(cnt);
return 0;
}
verified