落書きの魔女 (AOJ 2314)

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

問題

略

解法

解説参照。

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

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))

int h, w;
char field[20][20];
map<vector<char>, int> memo[20][20];

char mapto[10];
int calc(vector<char> connect, int x, int y);

int NextState(vector<char> connect, int x, int y, char c) {
  int ret = 0;
  int pc = connect[x];
  int lc = -1;
  if (x != 0) { lc = connect[x - 1]; }
  if (c == '#') {
    ret++;
    if (lc >= 0 && lc == pc) { return -1; }
    if (lc >= 0) {
      connect[x] = lc;
      if (pc >= 0) {
        REP(i, w) {
          if (connect[i] == pc) { connect[i] = lc; }
        }
      }
    } else if (pc == -1) {
      connect[x] = 9;
    } else {
      // do nothing
    }
  } else {
    if ((y != 0 && pc == -1) ||
        (x != 0 && lc == -1)) { return -1; }
    connect[x] = -1;
    if (pc != -1) {
      REP(i, w) {
        if (connect[i] == pc) { goto ok; }
      }
      return -1;
ok:;
    }
  }

  {
    // Normalize
    MEMSET(mapto, -1);
    int m = 0;
    REP(i, w) {
      if (connect[i] != -1) {
        if (mapto[(int)connect[i]] == -1) {
          mapto[(int)connect[i]] = m++;
        }
        connect[i] = mapto[(int)connect[i]];
      }
    }
    assert(m <= 8);
  }
  int nret = calc(connect, x + 1, y);
  if (nret == -1) { ret = -1; }
  else { ret += nret; }
  return ret;
}

int calc(vector<char> connect, int x, int y) {
  if (memo[y][x].count(connect)) { return memo[y][x][connect]; }
  if (y == h) {
    REP(x, w) {
      if (connect[x] > 0) { return -1; }
    }
    return 0;
  }
  if (x == w) { return calc(connect, 0, y + 1); }
  int ret = -1;
  if (field[y][x] == '?') {
    ret = max(ret, NextState(connect, x, y, '#'));
    ret = max(ret, NextState(connect, x, y, '.'));
  } else {
    ret = max(ret, NextState(connect, x, y, field[y][x]));
  }
  return memo[y][x][connect] = ret;
}

int main() {
  while (scanf("%d %d", &h, &w) > 0) {
    REP(y, 20) REP(x, 20) { memo[y][x].clear(); }
    REP(y, h) {
      int v = scanf("%s", field[y]);
      assert(v == 1);
    }
    int ans = -1;
    if (w == 1) {
      int cnt = 0;
      REP(y, h) { if (field[y][0] != '.') { cnt++; } }
      if (h == 2) { if (cnt != 0) { ans = cnt; } }
      else {
        ans = cnt;
        FOR(y, 1, h - 1) {
          if (field[y][0] == '.') { ans = -1; }
        }
      }
    } else {
      vector<char> connect(w, -1);
      ans = calc(connect, 0, 0);
    }
    printf("%d\n", ans);
  }
}