Y-game

Willy and Benny enjoy very much playing Y-game! This is a game in which white and black tokens are placed on a triangular n-grid, n 0, where n is called the order of the grid. A 3-grid is depicted in the figure below:

In general, an n-grid has (n + 2)(n + 1)/2 points with nonnegative ``baricentric coordinates'' (x, y, z), where x + y + z = n. Coordinates in a n-grid are assigned in such way that along right to left paths x-coodinates are constant, y-coordinates increase by one unit, and z-coordinates decrease by one unit (observe that this construction maintains x + y + z = n true). Symmetric situations may be observed for left to right (where y-coordinates are constant) and horizontal (where z-coordinates are constant) paths. A point (x, y, z) in a n-grid is said to lay on the x side (resp., y side, z side) if and only if x = 0 (resp., y = 0, z = 0).

Willy uses white tokens and Benny uses black ones. Y-game rules are rather complicated, but the end of the game is attained when there is a token placed on every node of the grid. The winner is that player that has formed a Y, that is, his/her tokens are so placed that they include a connected set of points with a point on each side. For example, the following figure represents an end situation where Benny wins:

The winner is rather easy to determine when the grid is small. But Willy and Benny are not interested in that discussion today. Actually, they just want a software solution that computes the winner of ended Y-games. Could you help them?

Input 

The problem input consists of several cases. A case begins with a line with two integer numbers, n and m, where n is the order of the grid and m the number of positions that have a black-coloured token (Benny's tokens), with 0 n 20 and 0 m (n + 2)(n + 1)/2.

Then, m lines follow, each one with 3 values x, y and z representing coordinate (x, y, z) of a point in the n-grid with a black token. Values on each input line are separated by one or more spaces.

The end of the input is signaled by a line

0 0

Output 

Output texts for each input case are presented in the same order that the input is read. For an input case in the puzzle statement, the output should be a single line with the left-justified text

Willy

or

Benny

accordingly to the fact that Willy or, respectively, Benny wins in that case.

Sample Input 

3 5
0 1 2
1 0 2
3 0 0
1 1 1
1 2 0
2 3
0 0 2
1 0 1
0 2 0
1 1
1 0 0
0 0

Sample Output 

Benny
Willy
Willy

---

題目描述：

給定一個盤面，問誰獲勝了。
獲勝方式為一個元件可以連到三角形的三條邊。

#include <stdio.h>
#include <string.h>
using namespace std;
int dx[] = { -1, +0, +1, +1, +0, -1 };
int dy[] = { +0, -1, -1, +0, +1, +1 };
int dz[] = { +1, +1, +0, -1, -1, +0 };
int g[25][25][25], used[405];
int x[405], y[405], z[405];
int X, Y, Z;
void dfs(int idx) {
    if(used[idx])    return;
    used[idx] = 1;
    X |= x[idx] == 0;
    Y |= y[idx] == 0;
    Z |= z[idx] == 0;
    for(int i = 0; i < 6; i++) {
        if(x[idx]+dx[i] < 0 || y[idx]+dy[i] < 0 || z[idx]+dz[i] < 0)
            continue;
        int v = g[x[idx]+dx[i]][y[idx]+dy[i]][z[idx]+dz[i]];
        if(v != -1)    dfs(v);
    }
}
int main() {
    int n, m;
    int i, j, k;
    while(scanf("%d %d", &n, &m) == 2 && n+m) {
        memset(g, -1, sizeof(g));
        memset(used, 0, sizeof(used));
        for(i = 0; i < m; i++) {
            scanf("%d %d %d", &x[i], &y[i], &z[i]);
            g[x[i]][y[i]][z[i]] = i;
        }
        int ret = 0;
        for(i = 0; i < m; i++) {
            if(used[i] == 0) {
                X = Y = Z = 0;
                dfs(i);
                ret |= X && Y && Z;
            }
        }
        puts(ret ? "Benny" : "Willy");
    }
    return 0;
}