wa了几次,至少要考虑4个方向:下、右、左下、右下。很像当年北航的机试题目。
/* 2699 */
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
using namespace std; #define MAXN 16 typedef struct node_t {
char x, y, d, c;
bool f;
node_t() {}
node_t(char xx, char yy, char dd, char cc, bool ff) {
x = xx; y = yy; d = dd; c = cc; f = ff;
}
} node_t; char map[MAXN][MAXN];
char n = ;
char ch;
char dir[][] = {
// right, down, diag(2)
, , ,, , , ,-
}; bool check(char x, char y) {
return x< || x>=n || y< || y>=n;
} bool bfs(char xx, char yy) {
queue<node_t> Q;
node_t nd;
char i, j, k;
char x, y; for (i=; i<; ++i) {
nd.x = xx + dir[i][];
nd.y = yy + dir[i][];
nd.d = i;
nd.c = ;
if (check(nd.x, nd.y))
continue;
if (map[nd.x][nd.y] == ch) {
nd.f = false;
Q.push(nd);
x = xx - dir[i][];
y = yy - dir[i][];
if (!check(x, y) && map[x][y]=='.') {
nd.f = true;
nd.c = ;
Q.push(nd);
}
} else if (map[nd.x][nd.y] == '.') {
nd.f = true;
Q.push(nd);
}
} while (!Q.empty()) {
nd = Q.front();
Q.pop();
if (nd.c==) {
return true;
}
nd.x += dir[nd.d][];
nd.y += dir[nd.d][];
if (check(nd.x, nd.y))
continue;
--nd.c;
if (map[nd.x][nd.y] == ch) {
Q.push(nd);
} else if (map[nd.x][nd.y]=='.' && nd.f==false){
nd.f = true;
Q.push(nd);
}
} return false;
} int main() {
int t, tt=;
int w, b;
char i, j, k;
bool flag; #ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif scanf("%d", &t);
while (t--) {
w = b = ;
for (i=; i<n; ++i) {
scanf("%s", map[i]);
for (j=; j<n; ++j) {
if (map[i][j] == 'W')
++w;
else if (map[i][j] == 'B')
++b;
}
}
ch = (w==b) ? 'B' : 'W';
flag = false;
for (i=; i<n; ++i) {
for (j=; j<n; ++j) {
if (map[i][j]==ch && bfs(i,j)) {
flag = true;
goto _output;
}
}
}
_output:
if (flag)
puts("YES");
else
puts("NO");
} return ;
}