Time Limit: 1 Second Memory Limit: 32768 KB``PATH" is a game played by two players on an N by N board, where N is a positive integer. (If N = 8, the board looks like a chess board.) Two players ``WHITE" and ``BLACK" compete in the game to build a path of pieces played on the board from the player's ``home" edge to the player's ``target" edge, opposite the home edge. WHITE uses white pieces and BLACK uses black pieces.
For this problem you will play the ``referee" for the game, analyzing boards containing black and white pieces to determine whether either of the players has won the game or if one of the players can win by placing one of their pieces in an unfilled position. WHITE's turn is next.
A representation of a board on paper (and in a computer) is an N x N matrix of characters 'W', 'B', and 'U'; where W represents white pieces, B represents black pieces, and 'U' represents unfilled positions on the board.
When we view a matrix representation of the board on paper, WHITE's home edge is the left edge of the board (the first column), and WHITE's target edge is the right edge (the last column). BLACK's home edge is the top edge of the board (the first row), and BLACK's target edge is the bottom edge (the last row). Thus WHITE wants to build a path from left to right, and BLACK wants to build a path from top to bottom.
Two locations on the board are ``adjacent" if one is immediately to the left, to the right above, or below the other. Thus an interior location on the board is adjacent to four other locations. For N > 1, corner locations each have two adjacent locations, and for N > 2, other border locations have three adjacent locations.
A path is a sequence of distinct positions on the board, L0, L1, ..., Lk, such that each pair Li and Li+1 are adjacent for i = 0, ..., k-1. A winning path for a player is a path L0, L1, ..., Lk filled with the player's pieces such that L0 is a position on the player's home edge and Lk is a position on the player's target edge. It is clear that if one player has a winning path then the other player is blocked from having a winning path. Thus if all the squares contain pieces, either there are no winning paths or exactly one of the players has at least one winning path.
Input is a series of game board data sets. Each set begins with a line containing
an integer specifying the size N, 0
As referee, for each game board in a series of game boards your program should
report one of the five types of answers below:
White has a winning path.
Black has a winning path.
White can win in one move. (White can place a piece in an unfilled position)
Black can win in one move. (White can't win in one move AND Black can)
There is no winning path.
7 WBBUUUU WWBUWWW UWBBBWB BWBBWWB BWWBWBB UBWWWBU UWBBBWW 3 WBB WWU WBB 0
White has a winning path. White can win in one move.Submit
Source: Pacific Northwest 1997