Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
Generalized Connect Four
 Time Limit: 6000MS Memory Limit: 131072K Total Submissions: 654 Accepted: 119 Case Time Limit: 2000MS

Description

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?

Input

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.

Output

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!

Sample Input

```4 5
.....
.....
.....
.BWB.```

Sample Output

`Draw!`

Hint

Consider using alpha-beta pruning.

Source

[Submit]   [Go Back]   [Status]   [Discuss]