fiveinarow_momodi.cpp

第四届百度杯预赛解题报告 武汉大学20090315

/*
 * Author: momodi
 * Created Time:  2/15/2009 10:52:08 AM
 * File Name: FiveInARow.cpp
 * Description: 
 It's a very easy problem, just do it!
 */
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define out(x) printf("%s: %I64d\n", #x, (long long)(x))
#define SZ(v) ((int)(v).size())
const int maxint=~0u>>1;
template <class T> void get_max(T& a, const T &b) {b > a? a = b:1;}
template <class T> void get_min(T& a, const T &b) {b < a? a = b:1;}
const int zi[] = {
    0, 1, 1, 1
};
const int zj[] = {
    1, 1, 0, -1
};
int dt[15][15];
bool ok(int i, int j) {
    return i >= 0 && i < 15 && j >= 0 && j < 15;
}
bool can_win() {
    for (int i = 0; i < 15; ++i) {
        for (int j = 0; j < 15; ++j) {
            if (dt[i][j] != 0) {
                for (int z = 0; z < 4; ++z) {
                    bool flag = true;
                    int ii = i, jj = j;
                    for (int k = 0; k < 5; ++k) {
                        if (!ok(ii, jj) || dt[ii][jj] != dt[i][j]) {
                            flag = false;
                            break;
                        }
                        ii += zi[z], jj += zj[z];
                    }
                    if (flag == true) {
                        return true;
                    }
                }
            }
        }
    }
    return false;
}
bool check(int k) {
    for (int i = 0; i < 15; ++i) {
        for (int j = 0; j < 15; ++j) {
            if (dt[i][j] == 0) {
                dt[i][j] = k;
                if (can_win()) {
                    return true;
                }
                dt[i][j] = 0;
            }
        }
    }
    return false;
}
bool win() {
    int a = 0;
    for (int i = 0; i < 15; ++i) {
        for (int j = 0; j < 15; ++j) {
            a += dt[i][j];
        }
    }
    if (a == 0) {
        return check(1);
    } else {
        return check(-1);
    }
}
int main() {
    int ca;
    scanf("%d", &ca);
    while (ca--) {
        char s[1000];
        for (int i = 0; i < 15; ++i) {
            scanf("%s", s);
            for (int j = 0; j < 15; ++j) {
                if (s[j] == 'B') {
                    dt[i][j] = 1;
                } else if (s[j] == 'W') {
                    dt[i][j] = -1;
                } else {
                    dt[i][j] = 0;
                }
            }
        }
        if (win()) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}