AtCoder Beginner Contest 317E

ABC317E

実装が少し面倒だが，ただの BFS.
前処理として，通れないマス全体を求めておくと楽． それさえ出来ていれば，グリッドに対する BFS をするだけ．

実装例:

公式解説の方法を載せる． 通れない頂点は，BFS で既に調べた頂点として初期化しておけばよい．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll h,w ; cin >> h >> w;

  vector<string> a(h);

  cinv(a);

  vector<char> v = {'>', 'v', '<', '^', '#'};

  vll dx = {0,1,0,-1};

  vll dy = {1,0,-1,0};

     

  vvll ng(h, vll(w));

  rep(x,h) rep(y,w) {

    if(in(a[x][y],v)) ng[x][y] = true;

    rep(i,4)if(a[x][y] == v[i]){

      ll nx = x;

      ll ny = y;

      while(true){

        nx += dx[i];

        ny += dy[i];

        if(!in(nx,h)) break;

        if(!in(ny,w)) break;

        if(in(a[nx][ny], v)) break;

        ng[nx][ny] = true;

      }

    }

  }

  ll sx, sy , gx , gy;

  rep(x,h) rep(y,w){

    if(a[x][y] == 'S') {

      sx = x;

      sy = y;

    }

    if(a[x][y] == 'G'){

      gx = x;

      gy = y;

    }

  }

  // BFS ----------------------------

  vvll dis(h, vll(w,INFL));

  queue<pll> que;

  auto push = [&](ll nx, ll ny, ll d) -> void {

    if(dis[nx][ny] != INFL) return;

    que.push({nx,ny});

    dis[nx][ny] = d;

  };

  push(sx, sy, 0);

  while(que.size()){

    auto [cx,cy] = que.front(); que.pop();

    ll d = dis[cx][cy];

    rep(i,4){

      ll nx = cx + dx[i];

      ll ny = cy + dy[i];

      if(!in(nx, h)) continue;

      if(!in(ny, w)) continue;

      if(!ng[nx][ny]) push(nx,ny, d+1);

    }

  }

  ll ans = dis[gx][gy];

  if(ans >= INFL) ans = -1;

  cout << ans << endl;

 

  return 0;

}