|Online Judge||Problem Set||Authors||Online Contests||User|
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,
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!”
4 5 ..... ..... ..... .BWB.
Consider using alpha-beta pruning.
POJ Founder Monthly Contest – 2008.03.16, Jiang Liyang
[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