Member SRM 485 Div2 Hard RectangleAvoidingColoringEasy

問題

グリッドが与えられる。各セルは白'W'か黒'B'か何も塗られていない'?'のいずれかである。'?'のセルを白か黒で塗っていきグリッドがRectangleAvoidingになるようにしたい。RectangleAvoidingとはグリッド中のいかなる長方形（各辺がXY軸に平行なもの）を取り出してもその頂点が4つとも同じ色ではないようになるグリッドである。
色の塗り方の総数を求めよ。

やりかた

rng_58さんの答えを参考にしました。

?の数が多いので全探索は間に合わない。そのため枝刈りしながら深さ優先探索。

今のセル（もしセルが'?'だったら白と黒に塗ってみて）の左上のグリッドがRectangleAvoidingであれば次の表に移って探索続行。
ここで左上のグリッドがRectangleAvoidingかどうかは今のセルを一つの頂点とする長方形についてのみ調べればいい。それいがいの可能性はその座標まで調べてきた段階で除外されているからである。

ある一定以上大きいグリッドではどうやってもRectangleAvoidingにはならないらしい。

以下ソース。

class RectangleAvoidingColoringEasy {
public:
  vector<string> fi;
  int N, M;
  int ans;
  bool rect(int y, int x){
    for(int i = 0; i < y; i++)
      for(int j = 0; j < x; j++)
	if(fi[i][j] == fi[i][x] && fi[i][j] == fi[y][j] && fi[i][j] == fi[y][x]) return false;
    return true;
  }
  void dfs(int y, int x){

    int ny = y, nx = x + 1;

    if(x == M && y < N){
      ny = y + 1; nx = 0;
    } 

    if(y == N){
      ans++;
      return;
    }

    if(fi[y][x] == '?'){
      fi[y][x] = 'W';
      if(rect(y, x)) dfs(ny, nx);
      fi[y][x] = 'B';
      if(rect(y, x)) dfs(ny, nx);
      fi[y][x] = '?';
    }else{
      if(rect(y, x)) dfs(ny, nx);
    }
    return;
  }
  int count(vector <string> board) {
    fi = board;
    ans = 0;
    N = board.size(); M = board[0].length();
    
    dfs(0, 0);
    return ans;
  }
};