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