Wu-Zi-Qi

Wu-Zi-Qi ( )

Problem Description
The game "wu-zi-qi"( ) is a game played by two people. The two player A and B take turns marking a dot at the unmarked intersection of an 20x20 grid. The color of the dots marked by A is black and the color of the dots marked by B is white. Initially、the chessboard is empty、which means that all the intersetions of the 20 grid are unmarked. The player who first marks 5 dots consecutively in a line wins. The line on which the winning player marked can be a horizontal line、a verticle line、or a diagonal line with slop 1 or -1.
Assume that the coordinates of the intersection of the 20x20 grid is denoted by (x; y)、where 0 <= x、y <= 19. Given a set of coordinates of the black dots、and a set of coordinates of the write dots、write a program to determine who wins the game.

Input Format
The inpute file contains many sets of test data. Each test data contains two lines、and each line conatins a set of coodinates of the dots marked by the player. The first line is for the player A and the second line is for player B. The last test data set is followed by (0、0) (0、0)、indicating the end of the file.

Output Format
For each test data set、print the winner of the game.

Sample Input
(2,3) (2,4) (2,5) (2,6) (2,7)
(3,3) (3,4) (3,5) (3,6)
(3,2) (4,2) (5,2) (6,2) (7,7)
(3,3) (4,3) (5,3) (6,3) (7,3)
(3,3) (4,4) (5,5) (6,6) (7,7)
(3,2) (4,2) (5,2) (6,2)
(3,2) (4,2) (5,2) (6,2)(1,1)
(2,14) (3,13) (4,12) (5,11) (6,10)
(0,0) (0,0)

Sample Output
A wins
B wins
A wins
B wins

困難度：*

時間複雜度：O(n^2)

解題原理：
1. 以字串讀入後進行處理，一次處理二行
2. 將字串座標進行分割後落子
3. 每一子有八個方向，分別為上、下、左、右、右上、右下、左上、左下，依序判斷是否連續落下五子

另解：
使用 dynamic programming，計算解決一個棋盤的問題等於分解 4 等份後再解決。
T(n) = 4T(n/4) + O(n)

程式下載

原碼下載

參考來源：中山大學 九十二學年度電腦程式設計競賽 試題 Problem 3