1. 


/* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #601 (The PATH)
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=542
*
* @author Dennis Wilfert
* @author Johann Studt
* @version 1.0, 06/25/2009
*
* Status : Accepted
* Runtime: 0.064
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
static char[][] field;
static boolean winner;
public static void main(String[] args) throws IOException {

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringBuilder output = new StringBuilder();
int size;

while(true){
// Größe des Feldes auslesen
size = Integer.parseInt(reader.readLine());
// Abbrechen wenn die Größe 0 ist
if(size==0)break;

reader.readLine();
// Char-Array für das Feld
field = new char[size][size];
// Zeigt an ob bereits einer der Fälle eingetreten ist
winner = false;
// Feld auslesen
for(int i = 0; i<size; i++){
field[i]=reader.readLine().toCharArray();
}
reader.readLine();
// Prüfen ob der weiße Spieler gewonnen hat
if(!winner){
for(int i =0; i<size;i++){
white(0, i, size);
}
if(winner)output.append("White has a winning path.\n");
}
// Prüfen ob der schwarze Spieler gewonnen hat
if(!winner){
for(int i =0; i<size;i++){
black(i, 0, size);
}
if(winner)output.append("Black has a winning path.\n");
}
// Prüfen ob der weiße Spieler in einem Zug gewinnen kann
if(!winner){
for(int i =0; i<size;i++){
whiteOneMove(0, i, size, false);
}
if(winner)output.append("White can win in one move.\n");
}
// Prüfen ob der schwarze Spieler in einem Zug gewinnen kann
if(!winner){
for(int i =0; i<size;i++){
blackOneMove(i, 0, size, false);
}
if(winner)output.append("Black can win in one move.\n");
}
// Keiner der beiden kann inerhalb eines Zuges gewinnen
if(!winner)output.append("There is no winning path.\n");
}
System.out.print(output);
}
/*
* Prüfen ob es einen Pfad für den weißen Spieler gibt
*/
static void white(int x, int y, int s){
// Ist x == s dann gibt es einen WinningPath
if(x==s){
winner=true;
}
else{
if(y>=0&&y<s&&x>=0)
// Enthält die aktuelle Position ein W, dann W auf X setzen,
// damit das Feld nicht mehr beachtet wird und anschließend auf die umliegenden
// Positionen gehen
if(field[y][x]=='W'){
field[y][x]='X';
white(x, y-1, s);
white(x, y+1, s);
white(x+1, y, s);
white(x-1, y, s);
}
}

}
/*
* Prüfen ob der weiße Spieler nach einem Zug gewinnen kann
*/
static void whiteOneMove(int x, int y, int s, boolean move){
// Ist x == s dann kann der Spieler nach einem Zug gewinnen
if(x==s){
winner=true;
}
else{
if(y>=0&&y<s && x>=0 && !winner){
// Ist an der aktuellen Position ein U und move noch auf
// false, dann kann der Spieler an diese Position ein W
// setzen.
if(!move && field[y][x]=='U'){
whiteOneMove(x, y-1, s, true);
whiteOneMove(x, y+1, s, true);
whiteOneMove(x+1, y, s, true);
whiteOneMove(x-1, y, s, true);
}
else{
// Ist move noch nicht gesetzt sind alle Positionen in denen ein X, W oder Y steht
// gültig, das aktuelle Feld wird auf Z gesetzt.
if(!move && (field[y][x]=='X' || field[y][x]=='W' || field[y][x]=='Y')){
field[y][x]='Z';
whiteOneMove(x, y-1, s, move);
whiteOneMove(x, y+1, s, move);
whiteOneMove(x+1, y, s, move);
whiteOneMove(x-1, y, s, move);
}
// Ist move Gesetzt sind Positionen mit X oder W gültig. Das Feld wird auf Y gesetzt
// damit aufrufe bei denen move noch auf false steht die Position noch finden
if(move && (field[y][x]=='X' || field[y][x]=='W')){
if(x==0){
move=false;
field[y][x]='Z';
}
else{
field[y][x]='Y';
}

whiteOneMove(x, y-1, s, move);
whiteOneMove(x, y+1, s, move);
whiteOneMove(x+1, y, s, move);
whiteOneMove(x-1, y, s, move);
}
}
}
}

}
/*
* Prüfen ob es einen Pfad für den schwarzen Spieler gibt
*/
static void black(int x, int y, int s){
// Ist y == s dann gibt es einen WinningPath
if(y==s){
winner=true;
}
else{
if(x>=0&&x<s && y>=0)
// Enthält die aktuelle Position ein B, dann B auf C setzen,
// damit das Feld nicht mehr beachtet wird und anschließend auf die umliegenden
// Positionen gehen
if(field[y][x]=='B'){
field[y][x]='C';
black(x+1, y, s);
black(x-1, y, s);
black(x, y+1, s);
black(x, y-1, s);
}
}

}
/*
* Prüfen ob der schwarze Spieler nach einem Zug gewinnen kann
*/
static void blackOneMove(int x, int y, int s, boolean move){
// Ist y == s dann kann der Spieler nach einem Zug gewinnen
if(y==s){
winner=true;
}
else{
if(x>=0&&x<s && y>=0 && !winner){
// Ist an der aktuellen Position ein U und move noch auf
// false, dann kann der Spieler an diese Position ein B
// setzen.
if(!move && field[y][x]=='U'){
blackOneMove(x+1, y, s, true);
blackOneMove(x-1, y, s, true);
blackOneMove(x, y+1, s, true);
blackOneMove(x, y-1, s, true);
}
else{
// Ist move noch nicht gesetzt sind alle Positionen in denen ein C, B oder D steht
// gültig, das aktuelle Feld wird auf E gesetzt.
if(!move && (field[y][x]=='C' || field[y][x]=='B' || field[y][x]=='D')){
field[y][x]='E';
blackOneMove(x+1, y, s, move);
blackOneMove(x-1, y, s, move);
blackOneMove(x, y+1, s, move);
blackOneMove(x, y-1, s, move);
}
// Ist move Gesetzt sind Positionen mit C oder B gültig. Das Feld wird auf D gesetzt
// damit aufrufe bei denen move noch auf false steht die Position noch finden
if(move && (field[y][x]=='C' || field[y][x]=='B')){
if(y==0){
move=false;
field[y][x]='E';
}
else{
field[y][x]='D';
}
blackOneMove(x+1, y, s, move);
blackOneMove(x-1, y, s, move);
blackOneMove(x, y+1, s, move);
blackOneMove(x, y-1, s, move);
}
}
}
}

}

}