AtCoder Beginner Contest 211E

ABC211E

BFS で全探索． 丁度 \(k \in K\) マス塗っている状態全体を，入れ物 \(q\) に入れる． \(q\) の中から，次の1マスを塗って遷移すると，丁度 \(k+1\) マスを塗った状態となる．

実装
塗ったマス全体の集合を \(2^{N^{2}}\) で管理する． long long で収まる． bit で管理するので，符号付き整数でも符号無し整数でも構わない．

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

int main() {

  ll n, k ;

  cin >> n >> k;

  vector<string> s(n); cinv(s);

  set<ll> q; // ll : 塗った升目 \in 2^{n^{2}}

  rep(x,n) rep(y,n) if(s[x][y] == '.') q.insert(1LL << (x*n + y));

  srep(_, 1, k){

    set<ll> ne;

    for(auto cu: q){

      rep(x,n) rep(y,n) if(s[x][y] == '.' && !(cu & (1LL << (x*n + y)))){

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

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

        rep(d,4){

          ll nx = dx[d] + x;

          ll ny = dy[d] + y;

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

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

          if(s[nx][ny] == '.' && (cu & (1LL << (nx*n + ny)))){

            ne.insert(cu | (1LL << (x*n + y)));

            break;

          }

        }

      }

    }

    swap(q, ne);

  }

 

  cout << q.size() << endl;

  return 0;

}