perogram

bfsのたたき台

  • 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;
    }
  }
  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];
}