HE Filler Game ( SG )

Filler Game | Dynamic Programming and Bit Masking & Algorithms Practice Problems | HackerEarth

題意：
一個 N * M 的棋盤，一開始也許會有障礙物。輪流操作放置一個障礙物，一個格子可以放障礙物若且唯若它是空的，而且它有一個相鄰的格子是空的。問先手輸贏。

制約：
1 ≤ N * M ≤ 20
1 ≤ Q ≤ 5e4

解法：
由於至多只有 20 個格子，所以至多 2 ** 20 種狀態。暴力 SG 就可以了。

時間 / 空間複雜度：
O( 2 ** ( N * M ) * N * M ) / O( 2 ** ( N * M ) )

#include <bits/stdc++.h>
using namespace std;
 
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
 
int N, M, Q;
 
int sg[ 1 << 20 ];
 
int dfs( int state ) {
  if( sg[ state ] != -1 ) return sg[ state ];
  set< int > bag;
  for( int i = 0; i < N * M; ++i ) {
    if( state >> i & 1 ) continue;
    int x = i / M;
    int y = i % M;
    for( int di = 0; di < 4; ++di ) {
      int nx = x + dx[ di ];
      int ny = y + dy[ di ];
      if( not ( 0 <= nx and nx < N and 0 <= ny and ny < M ) ) continue;
      int t = nx * M + ny;
      if( state >> t & 1 ) continue;
      bag.emplace( dfs( state | 1 << i ) );
      break;
    }
  }
  for( int i = 0; ; ++i ) {
    if( not bag.count( i ) ) {
      return sg[ state ] = i;
    }
  }
}
 
signed main() {
  ios::sync_with_stdio( 0 );
  memset( sg, -1, sizeof( sg ) );
  cin >> N >> M >> Q;
  for( int qi = 0; qi < Q; ++qi ) {
    int state = 0;
    for( int i = 0; i < N; ++i ) {
      string line;
      cin >> line;
      for( int j = 0; j < M; ++j ) {
        state = state * 2 + line[ j ] - '0';
      }
    }
    cout << ( dfs( state ) == 0 ) << "\n";
  }
  return 0;
}