Instantly share code, notes, and snippets.

@maksverver /B-dp.cc Secret
Created Jan 11, 2016

Embed
What would you like to do?
Facebook Hacker Cup 2016 Qualification Round problem B: High Security
#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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment