AtCoder Beginner Contest 311D

ABC311 D

BFS で求まる． 訪れたマスを記録しておいて，1回しか調べないことにする． ただし，通過したマスと止まったマスは区別する．
遷移するとき，ぶつかるまで一気に進むので while 文で実装する．

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

int main() {

  vll n(2); cinv(n);

  vector<string> s(n[0]);

  cinv(s);

  queue<vll> q;

  vvvll vis(n[0], vvll(n[1], vll(2)));

  q.push({1,1});

  while(q.size()){

    vll cx = q.front(); q.pop();

    if(vis[cx[0]][cx[1]][1]) continue;

    vis[cx[0]][cx[1]][1] = true;

    vvll dx(2);

    dx[0] = {-1,0,1,0};

    dx[1] = {0,-1,0,1};

    rep(i,4){

      vll nx = cx;

      while(true){

        rep(s,2) nx[s] += dx[s][i];

        bool f = true;

        rep(s,2) f &= in(nx[s], n[s]);

        if(!f) break;

       

        if(s[nx[0]][nx[1]] != '#') {

          vis[nx[0]][nx[1]][0] = true;

        }else{

          rep(s,2) nx[s] -= dx[s][i];

          q.push(nx);

          break;

        }

      }

    }

  }

  ll ans = 0;

  rep(x,n[0]) rep(y,n[1]) {//if(s[x][y] != '#'){

    ll t = (vis[x][y][0] || vis[x][y][1]);

    ans += t;

  }

  cout << ans << endl;

  return 0;

}