2015年3月16日 星期一

2015/03/16 TIOJ 1046 . B.陷阱

// http://tioj.ck.tp.edu.tw/problems/1046
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

#define INF 2000000000

char c[10][10];
char d[10][10];

int vx[] = { 0, -1, 0, 1};
int vy[] = { -1, 0, 1, 0};

int n, m, cnt;

void push(int x, int y)
{
    cnt++;
    d[x][y] = 'O'+'X'-d[x][y];

    for(int vi = 0; vi < 4; vi++)
    {
        int nx = x+vx[vi];
        int ny = y+vy[vi];

        if( 0 > nx || nx >= n ) continue;
        if( 0 > ny || ny >= m ) continue;

        d[nx][ny] = 'O'+'X'-d[nx][ny];
    }
}

int main()
{
    while(1)
    {
        n = 0;

        for(; ; n++)
        {
            strcpy(c[n], "");
            scanf("%[^\n]", c[n]);
            getchar();

            if( !strcmp(c[n], "#") ) return 0;
            if( !strcmp(c[n], "") ) break;
        }

        if( !n ) continue;

        m = strlen(c[0] );

        int Ans = INF;

        for(int i = 0; i < (1<<m); i++)
        {
            cnt = 0;

            for(int ni = 0; ni < n; ni++)
                strcpy(d[ni], c[ni]);

            int p = i;

            for(int j = 0; p; j++)
            {
                if( p&1 ) push(0, j);
                p >>= 1;
            }

            for(int ni = 1; ni < n; ni++)
                for(int mi = 0; mi < m; mi++)
                    if( d[ni-1][mi] == 'O' )
                        push(ni, mi);

            bool OK = true;

            for(int mi = 0; mi < m; mi++)
                if( d[n-1][mi] == 'O' ) OK = false;

            if( OK ) Ans = min(Ans, cnt);
        }

        if( Ans == INF ) puts("Another Skeleton in the Ancient Tomb!");
        else printf("Minimum Steps : %d\n", Ans);

    }
}

沒有留言:

張貼留言