leetcode-go/poj/1185.artillery-position/main.cc

#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 100;
const int M = 10;
const int S = 60;

char row[M + 1]; // Stores each row of map
int map[N]; // Bitmap of each row, 1 stands for hill
int st[S], s; // All valid state
int dp[N][S][S]; // dp[i][j][k] means max cnt at row i, when row i at state j and row i-1 at state k

int n, m;

void init_state() {
  s = 0;
  for (int i = 0; i < 1 << m; i++) {
    if ((i << 1) & i || (i << 2) & i) continue;
    st[s++] = i;
  }
}

int ones(int i) {
  int cnt = 0;
  for (; i != 0; i >>= 1) i & 1 && cnt++;
  return cnt;
}

int main() {
  scanf("%d %d", &n, &m);
  memset(map, 0, sizeof(map));
  for (int i = 0; i < n; i++) {
    scanf("%s", row);
    for (int j = 0; j < m; j++) {
      map[i] <<= 1;
      if (row[j] == 'H') map[i] |= 1;
    }
  }
  init_state();
  memset(dp, 0xFF, sizeof(dp));
  for (int i = 0; i < s; i++) // Init dp[0][][]
    if ((map[0] & st[i]) == 0) dp[0][i][0] = ones(st[i]);
  for (int i = 0; i < s; i++) { // Init dp[1][][]
    if ((map[1] & st[i]) != 0) continue;
    for (int j = 0; j < s; j++) {
      if ((st[i] & st[j]) != 0 || dp[0][j][0] == -1) continue;
      dp[1][i][j] = max(dp[1][i][j], dp[0][j][0] + ones(st[i]));
    }
  }
  for (int i = 2; i < n; i++) {
    for (int j = 0; j < s; j++) {
      if ((map[i] & st[j]) != 0) continue;
      for (int k = 0; k < s; k++) {
        if ((st[j] & st[k]) != 0) continue;
        for (int l = 0; l < s; l++) {
          if ((st[j] & st[l]) != 0 || dp[i - 1][k][l] == -1) continue;
          dp[i][j][k] = max(dp[i][j][k], dp[i - 1][k][l] + ones(st[j]));
        }
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < s; j++)
      for (int k = 0; k < s; k++) ans = max(ans, dp[i][j][k]);
  printf("%d\n", ans);
  return 0;
}