AOJ0091 Blur

問題
にじみ | Aizu Online Judge

布に染料を垂らす。染料は小中大の三種類あり、それぞれ広がる幅が異なる。
N滴落とした布の状態が与えられるので、染料を落とした座標を復元せよ。
染料は同じ場所に何度も落とすことが出来る。
N <= 12

解説
先ず愚直に再帰のコードを書き、染料を1つずつ回収していく。
左上から右下にループし、各座標について3種類のどの染料が使用されたかを試す。
自明な枝刈りとして、最大N滴までを利用して刈ること、染料を回収できなければ刈ることがある。
加えて、染料を落とす座標(x, y)について対して、(x-2, y-2)の場所に落とされた染料が回収しきれていなければ、
（右下に再帰が進行することから）二度と(x-2, y-2)の場所に落とされた染料を回収することは出来ない。
この枝刈りを加えればACすることが出来る。

const bool M[3][5][5] = {
{
  {0,0,0,0,0},
  {0,0,1,0,0},
  {0,1,1,1,0},
  {0,0,1,0,0},
  {0,0,0,0,0},
},
{
  {0,0,0,0,0},
  {0,1,1,1,0},
  {0,1,1,1,0},
  {0,1,1,1,0},
  {0,0,0,0,0},
},
{
  {0,0,1,0,0},
  {0,1,1,1,0},
  {1,1,1,1,1},
  {0,1,1,1,0},
  {0,0,1,0,0},
},
};

int G[10][10];

bool check(int k, int y, int x) {
  REP(i, -2, 3) REP(j, -2, 3) {
    if(M[k][2+i][2+j]) {
      if(!in_range(y+i, x+j, 10, 10)) return false;
      if(!G[y+i][x+j]) return false;
    }
  }
  return true;
}

void use(int k, int y, int x) {
  REP(i, -2, 3) REP(j, -2, 3) if(M[k][2+i][2+j])
    G[y+i][x+j] --;
}

void revive(int k, int y, int x) {
  REP(i, -2, 3) REP(j, -2, 3) if(M[k][2+i][2+j])
    G[y+i][x+j] ++;
}

bool cleared() {
  bool ok = 1;
  rep(i, 10) rep(j, 10) {
    ok &= G[i][j] == 0;
  }
  return ok;
}

bool invalid(int y, int x) {
  if(y-2 >= 0 && x-2 >= 0 && G[y-2][x-2]) return 1;
  return 0;
}

bool solve(int r, int y, int x) {
  if(y == 10) return r == 0 && cleared();
  if(invalid(y, x)) return 0;
  if(r && G[y][x]) {
    rep(k, 3) {
      if(check(k, y, x)) {
        use(k, y, x);
        if(solve(r - 1, y, x)) {
          cout << x << ' ' << y << ' ' << k + 1 << endl;
          return 1;
        }
        revive(k, y, x);
      }
    }
  }
  return solve(r, y + (x == 9), (x + 1) % 10);
}

int main() {

  int N; cin >> N;
  rep(i, 10) rep(j, 10) {
    cin >> G[i][j];
  }

  solve(N, 0, 0);
  
  return 0;
}