3527：Generalized Connect Four

You may have had fun with the popular board game Connect Four, especially if you are using GNOME or KDE, where the game comes under the name Four-in-a-Row or KFourInLine. Wikipedia describes the game as saying,

“Connect Four (also known as Plot Four, Four in a Row, and Four in a Line) is a two-player board game in which the players take turns in dropping alternating colored discs into a seven-column, six-row vertically-suspended grid. The object of the game is to connect four singly-colored discs in a row -- vertically, horizontally, or diagonally -- before your opponent can do likewise.”

The game was solved in 1988 by James D. Allen, and independently by Victor Allis. The first player can force a win with perfect play.

Slightly generalizing the game, we now use a m-column, n-row grid in the game. Starting from any legal position, can you decide whether any player can force a win or the game will end in a draw?

The input consists of a single test case. The first line contains m and n (1 ≤ m, n ≤ 10). Next come n lines each containing a string of m characters, which describes a legal position in the game. We use black (‘B’) and white (‘W’) discs in this problem. Unoccupied positions in the grid is denoted by periods (‘.’). At most 40 or 60% of all positions are unoccupied.

The first player always plays black discs when the game starts, but the given position may be continued with the second player playing first.

If the first player, who plays black discs, can force a win, output “Black Wins!”; if the second player, who plays white discs, can force a win, output “White Wins!”; otherwise, output “Draw!”

Consider using alpha-beta pruning.