High Security

問題

$2 \times W$の盤面が与えられる。各マスは空きマスまたは障害物である。 ここに警備員を何人か配置する。 警備員は4方向に十分長いの視界を持っている。将棋の飛車だと思えばよい。 全ての空きマスを監視するとき、警備員は最低何人必要か。

解法

縦幅が$2$しかないので貪欲。 $O(W)$。 警備員の上下への視界が結果に影響するのは、左右に障害物を持つ空きマスに関してのみであることを使う。

実装

#include <iostream>
#include <vector>
#include <array>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
using namespace std;
void solve() {
    int n; cin >> n;
    array<string,2> s; cin >> s[0] >> s[1];
    s[0] = "X" + s[0] + "X";
    s[1] = "X" + s[1] + "X";
    int ans = 0;
    repeat (y,2) {
        for (int l = 1; l <= n; ++l) {
            if (s[y][l] == 'X') continue;
            int r = l+1;
            while (s[y][r] != 'X') ++ r;
            if (r-l == 1) continue;
            repeat_from (x,l,r) {
                if (s[(y+1)%2][x-1] == 'X' and s[(y+1)%2][x] == '.' and s[(y+1)%2][x+1] == 'X') {
                    s[(y+1)%2][x] = 'X';
                    break;
                }
            }
            repeat_from (x,l,r) s[y][x] = 'X';
            ans += 1;
            l = r;
        }
    }
    repeat_from (x,1,n+1) {
        if (s[0][x] == '.' or s[1][x] == '.') {
            ans += 1;
        }
    }
    cout << ans << endl;
}
int main() {
    int testcases; cin >> testcases;
    repeat (testcase, testcases) {
        cout << "Case #" << testcase+1 << ": ";
        solve();
    }
    return 0;
}