Facebook Hacker Cup 2016 Qualification Round problem B: High Security

B-dp.cc

#include <assert.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
using namespace std;

enum RowState { CLOSED = 0, GUARDED = 1, OPEN = 2 };

static int N;
static vector<char> blocked[2];
static vector<int> memo;

const int inf = 999999999;

RowState Extend(RowState state, bool blocked, bool guard_here, bool guard_adjacent) {
  assert(!blocked || !guard_here);
  if (guard_here) return GUARDED;
  if (blocked) return CLOSED;
  if (state == GUARDED) return GUARDED;
  if (guard_adjacent) return state;
  return OPEN;
}

int Search(int col, RowState top, RowState bot) {
  const bool top_blocked = col == N || blocked[0][col];
  const bool bot_blocked = col == N || blocked[1][col];
  if (top_blocked && top == OPEN) return inf;
  if (bot_blocked && bot == OPEN) return inf;
  if (col == N) return 0;

  int &m = memo[9*col + 3*top + bot];
  if (m >= 0) return m;
  int res = inf;
  for (int guard_top = 0; guard_top < 2; ++guard_top) {
    for (int guard_bot = 0; guard_bot < 2; ++guard_bot) {
      if (guard_top && top_blocked) continue;
      if (guard_bot && bot_blocked) continue;
      const RowState new_top = Extend(top, top_blocked, guard_top, guard_bot);
      const RowState new_bot = Extend(bot, bot_blocked, guard_bot, guard_top);
      int cost = Search(col + 1, new_top, new_bot) + guard_top + guard_bot;
      res = min(res, cost);
    }
  }
  return m = res;
}

int main() {
  int T = 0;
  cin >> T;
  for (int t = 0; t < T; ++t) {
    cin >> N;
    for (int row = 0; row < 2; ++row) {
      string line;
      cin >> line;
      assert(line.size() == N);
      blocked[row].resize(N);
      for (int col = 0; col < N; ++col) blocked[row][col] = line[col] == 'X';
    }
    memo.assign(9*N, -1);
    cout << "Case #" << t + 1 << ": " << Search(0, CLOSED, CLOSED) << endl;
  }
}