UVA-260 - Il Gioco dell'X

• UVa Online Judge 解題結果請於 Submit 後，參閱 uHunt。
• 如果你有任何建議與指教，歡迎於下方留言一起討論喔！

題意概要

有兩方 (黑方與白方) 輪留在一個 $N \times N$ 的平行四邊形格中放入黑色與白色的棋子。如果黑方能建立一個由 $1$ - $N$ 行的連線，則黑方獲勝，否則由白方獲勝。白方獲勝的條件是要能建立一個由 $1$ - $N$ 的列的連線，由於此遊戲不能有平手的狀況，因此每次只能是其中一方勝出。

• 分析：本題為簡單的「深度優先搜尋 (DFS)」應用。由題目給定的獲勝條件，如果黑方要獲勝，可以直接由「行的方向 (由上至下)」進行 DFS 判斷即可；反之，如果白方要獲勝，可以直接由「列的方向 (由左至右)」進行 DFS 判斷即可。

Input

The input is a text file containing a number of games. Each game is given by: one line containing an integer $N$, being the number of rows. ($N$ can he any number between $2$ and $200$). This line is followed by $N$ lines, each consisting of a row of $N$ characters from the set {b, w} denoting the pawns of Black and White respectively. The numbers of black and white pawns will differ by at most one. Note that all positions on the board are filled with pawns. The list of games ends with a single zero on a line of its own. (Of course, this is not a game for which a winner has to be determined.)

Output

The output will be a textfile containing one line for each game. This line should contain the number of the game (starting at $1$) followed by a space, and followed by an uppercase B if Black did win, or followed by an uppercase W if White did win.

Sample Input

4
bbwb
wwbw
bbwb
bwww
4
bbwb
wwbw
bwwb
wwbb
0

Sample Output

1 W
2 B