bfsのたたき台 (2次元グリッド)

ライブラリ
  • bfsってやるだけなんだけど、これまで汎用化していなかった
  • たたき台としてここに書いておく

verified

code

VS S; // map
const int H_MAX = 55; // 1050とかでも通る
ll d[H_MAX][H_MAX];
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;
  }
}

// 問題設定に沿って書き換える
const char block = '#';
const char pass = '.';

// 引数は(Y, X), (Y, X)
// 0-indexed
// Yが先だからね！！
ll bfs(PII from, PII to){
  rep(i,H_MAX){
    rep(j,H_MAX){
      d[i][j]=-1; // 到達不能をinfにするか-1にするかは注意！
    }
  }
  queue<PII> que;
  d[from.first][from.second] = 0;
  que.push(from);
  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) && d[ny][nx]==-1 && S[ny][nx]!=block){
        // can go
        d[ny][nx] = d[pa.first][pa.second] + 1;
        que.push(MP(ny,nx));
      }
    }
  }
  return d[to.first][to.second];
}

aを見つけたらbに塗るbfs

    // search : 探す記号
    // paint : 塗り後の値
    auto fill_edge = [&](PII start, ll search, ll paint){
      if(G[start.first][start.second]!=search)return;
      
      queue<PII> que;
      que.push(start);
      G[start.first][start.second]=paint;

      while(!que.empty()){
        auto pa = que.front(); que.pop();
        ll y = pa.first;
        ll x = pa.second;
        rep(i,4){
          ll ny = y + dy[i];
          ll nx = x + dx[i];
          if(!in_range(ny,nx))continue;
          if(G[ny][nx]==search){
            que.push({ny,nx});
            G[ny][nx]=paint;
          }
        }
      }
    };