連結判定 bfs

  • やるだけ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;
  // startからbfsして全部埋められるか
  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);

    // input
    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