Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Generalized Connect Four
Time Limit: 6000MSMemory Limit: 131072K
Total Submissions: 608Accepted: 119
Case Time Limit: 2000MS


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!

Sample Input

4 5

Sample Output



Consider using alpha-beta pruning.


[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