2015年11月1日 星期日

2015/11/01 UVA 12987 - Ancient Go

/* https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=862&page=show_problem&problem=4870 */
/*
    DFS
    如果有任何一塊'o'
    周圍只有一個'.'

    就輸出 Can kill in one move!!!
    否則輸出 Can not kill in one move!!!
*/
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

typedef pair<int, int> xy;
#define x first
#define y second

vector<xy> v;
char c[9][10];
bool visit[9][9];

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

void DFS(int x, int y)
{
    if( c[x][y] == '.' ) v.push_back(xy(x, y) );
    if( c[x][y] != 'o' ) return;

    visit[x][y] = true;

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

        if( 0 > nx || nx >= 9 ) continue;
        if( 0 > ny || ny >= 9 ) continue;

        if( visit[nx][ny] ) continue;

        DFS(nx, ny);
    }
}

int main()
{
    int T;
    scanf("%d", &T);

    for(int Ti = 1; Ti <= T; Ti++)
    {
        fill(visit[0], visit[8]+9, false);

        for(int i = 0; i < 9; i++)
            scanf("%s", c[i]);

        bool flag = false;

        for(int i = 0; i < 9 && !flag; i++)
            for(int j = 0; j < 9 && !flag; j++)
                if( c[i][j] == 'o' && !visit[i][j] )
                {
                    v.clear();
                    DFS(i, j);

                    sort(v.begin(), v.end());
                    v.resize(unique(v.begin(), v.end())-v.begin());

                    if( v.size() == 1 ) flag = true;
                }

        printf("Case #%d: ", Ti);

        if( flag ) puts("Can kill in one move!!!");
        else puts("Can not kill in one move!!!");
    }
}

沒有留言:

張貼留言