[FHC 2016 Qualification Round]High Security

首先可以把每一條橫向的空格都塞一個守衛
那麼甚麼情況下可以讓一個守衛擔任兩個守衛的工作呢?
大概就只有一條長度1的空格對面也是空格的情況了吧
這時候，我們可以把那佔據一個空格的守衛移出來，取代對面的守衛，絕對不會吃虧
實作的話可以先找出所有"X.X"，讓守衛站出來，然後把看守到的區域標記掉
接著，再掃一遍，把所有未看守的地區再補上一個守衛
不知道這樣的貪心法有沒有例外，真正的結果要等比賽結束才知道Orz

ps.最後四題全對耶真開心 :D

code:

#include<cstdio>
#include<cassert>
#define scanf(x,...) assert(scanf(__VA_ARGS__)==x)
using namespace std;
int N;
char S[2][1002];
int main()
{
    freopen("Bin","r",stdin);
    freopen("out.txt","w",stdout);
    static int testcase;scanf(1,"%d",&testcase);
    while(testcase--)
    {
        scanf(1,"%d",&N);
        assert(N<=1000);
        scanf(2,"%s%s",S[0]+1,S[1]+1);
        S[0][0]=S[1][0]=S[0][N+1]=S[1][N+1]='X';
        for(int d=0;d<2;d++)for(int i=0;i<=N+1;i++)assert(S[d][i]=='X'||S[d][i]=='.');
        int ans=0;
        for(int d=0;d<2;d++)
        {
            for(int i=1;i<=N;i++)
            {
                if(S[d][i-1]=='X'&&S[d][i]=='.'&&S[d][i+1]=='X')
                {
                    S[d][i]='X',ans++;
                    if(S[d^1][i]=='.')
                    {
                        S[d^1][i]='X';
                        for(int j=i+1;S[d^1][j]=='.';j++)S[d^1][j]='X';
                        for(int j=i-1;S[d^1][j]=='.';j--)S[d^1][j]='X';
                    }
                }
            }
        }
        for(int d=0;d<2;d++)
        {
            for(int i=1;i<=N;i++)if(S[d][i]=='.')
            {
                ans++;
                for(int j=i;S[d][j]=='.';j++)S[d][j]='X';
            }
        }
        for(int d=0;d<2;d++)for(int i=0;i<=N+1;i++)assert(S[d][i]=='X');
        static int kase=1;
        printf("Case #%d: %d\n",kase++,ans);
    }
    scanf(-1,"%d",&testcase);
    return 0;
}