Mod 3 Knights Out (AOJ 2280)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2280

問題

略

解法

解説参照。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

const ll MOD = 1000000007;
const int dx[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
const int dy[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };

typedef vector<int> Array;
typedef vector<Array> Matrix;

void PrintMatrix(const Matrix &matrix) {
  REP(y, matrix.size()) {
    REP(x, matrix[0].size()) {
      if (x != 0) { putchar(' '); }
      printf("%d", matrix[y][x]);
    }
    puts("");
  }
}

void Put(Matrix &field, Matrix &knight, int y, int x, int cnt) {
  int h = field.size();
  int w = field[0].size();
  REP(dir, 8) {
    int nx = x + dx[dir];
    int ny = y + dy[dir];
    if (nx < 0 || nx >= w || ny < 0 || ny >= h) { continue; }
    field[ny][nx] = (field[ny][nx] + cnt + 3) % 3;
  }
  knight[y][x] += cnt;
  assert(!(cnt == 1) || knight[y][x] == 0 || knight[y][x] == 1);
}

int LastCheck(const Matrix &field, int endY, int offset) {
  int w = field[0].size();
  FOR(y, endY - 2, endY) {
    offset ^= 1;
    for (int x = offset; x < w; x += 2) {
      if (field[y][x] != 0) {
        return 0;
      }
    }
  }
  return 1;
}

int Check(const Matrix &field, int y, int x) {
  int w = field[0].size();
  if (y <= 1) { return 1; }
  if (x != 0 && field[y - 2][x - 1] != 0) { return 0; }
  if (x == w - 2 && field[y - 2][x + 1] != 0) { return 0; }
  return 1;
}

ll calc(Matrix &field, Matrix &knight, int y, int x) {
  int h = field.size();
  int w = field[0].size();
  if (y == h) {
    return LastCheck(field, y, x);
  }
  if (x >= w) {
    int nx = x % w;
    if (w % 2 == 0) { nx ^= 1; }
    return calc(field, knight, y + 1, nx);
  }
  ll ret = 0;
  if (Check(field, y, x)) {
    ret += calc(field, knight, y, x + 2);
  }
  Put(field, knight, y, x, 1);
  if (Check(field, y, x)) {
    ret += calc(field, knight, y, x + 2);
  }
  Put(field, knight, y, x, -1);
  return ret;
}

int solve(Matrix field) {
  int h = field.size();
  int w = field[0].size();
  ll ans = 0;
  if (w == 1 || h == 1) {
    REP(y, h) REP(x, w) {
      if (field[y][x] != 0) { return 0; }
    }
    ans = (1LL << (w * h)) % MOD;
  } else {
    Matrix knight(h, Array(w, 0));
    ll left = calc(field, knight, 0, 0);
    ll right = calc(field, knight, 0, 1);
    ans = left * right;
  }
  return ans;
}

int main() {
  int w, h;
  scanf("%d %d", &h, &w);
  Matrix field(h, Array(w, 0));
  REP(y, h) {
    REP(x, w) {
      scanf("%d", &field[y][x]);
    }
  }
  cout << solve(field) << endl;
}