Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Generalized Connect Four
Time Limit: 6000MSMemory Limit: 131072K
Total Submissions: 644Accepted: 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]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator