编程介的小学生 2017-04-27 15:30 采纳率: 20.5%
浏览 1575
已采纳

Gobang

Gobang is a game played on 15*15 board by two players. One player uses black stones, the other uses white stones. The game begins in an empty board and the two players place black stones and white stones on the intersections alternatively. Each intersection can place only one stone at most. For simplicity we just call the player who uses black stones Black and call the other player White. Black always goes first. There are 15 horizontal lines and 15 vertical lines in the board and the stones are placed on the intersections of the lines. Horizontal lines are marked 1, 2, . . . , 15 from up to down and vertical lines are marked 1, 2, . . . , 15 from left to right.

  The objective of this game is to make five stones of the same color consecutively along a horizontal, vertical, or diagonal line. 
  It's very simple isn't it? If rules are so simple like this there is a Black winning strategy (Black can win no matter how White will play the game). So the rules demand that if Black makes some particular patterns on the board he(or she) would lose the game. (White Wins the game. ) 
  We called a Black's step to make a forbidden pattern on the board prohibit-step. 

Then let me introduce the gobang rules to you. For simplicity I will define some patterns first.
For simplicity let's think that the board has a "virtual boundaries": Row 0 ,Row 16,Column 0 and Column 16.
(1) A pair of integers (x,y) indicates the intersection of Row x and Column y.
(2) Use term "virtual intersection" to indicate an intersection on the "virtual boundaries". (i.e. x=0 or y=0 or x=16 or y=16). (Of course no player can place stones on "virtual intersections" for they don't exist in the real board. )
(3) Use term "real intersection" to indicate an intersection on the real board. (i.e. 0<x<16 and 0<y<16)
(4) Use term "empty intersection" to indicate a real intersection on which no players have placed a stone.
(5) Use term "black intersection" to indicate a real intersection on which Black has placed a stone.
(6) Use term "white intersection" to indicate a real intersection on which White has placed a stone.

To define patterns well I use character "B" to indicate a black intersection.
(1) Use character "W" to indicates a white intersection.
(2) Use character "E" to indicates an empty intersection.
(3) Use character "*" as a wildcard which indicate a virtual intersection, white intersection or empty intersection.
(4) Use character "." as another wildcard which indicate ANY INTERSECTION (virtual intersection, black intersection ,white intersection, empty intersection)

Then Let me define 3 patterns:
1. Win pattern:
If after a player's step the Win pattern appears on the board the player makes this step will win the game.
(1) White Win pattern: a line of five OR MORE consecutive white stones. (White Win pattern: .WWWWW.)
(2) Black Win pattern: a line of exactly five consecutive black stones. (Black Win pattern: BBBBB)
2. Four pattern:(Only for Black)
I want to define two kinds of Four patterns.
(1) Four-I pattern: a line of four consecutive black stones and if we add a black stone on either end then it becomes a Black Win pattern. (Four-I pattern: EBBBBE)
(2) Four-II pattern: Removing one black stone in the Black Win pattern makes a Four-II pattern. (Four-II pattern: EBBBB,*BEBBB* and so on)
3. Three pattern: (Only for Black)
Removing one black stone in the Four-I pattern makes a May-Three pattern. (May-Three pattern EEBBBE,*EBEBBE* and so on)
Note: In the May-Three pattern there is AT LEAST ONE empty intersection on which if placing a black stone, the result pattern will be a Four-I pattern. A May-Three pattern is a Three pattern if and only if there is an empty intersection in the May-Three pattern on which placing a black stone is NOT a prohibit-step to make a Four-I pattern
Note: The definition of Three pattern uses the definition of prohibit-step which will be defined following:
(1) If after Black placing a stone on one intersection, there is a line of SIX OR MORE consecutive black stones which include the new placed stone on the board it is a long-link prohibit.
(2) If after Black placing a stone on one intersection, there appears two Four-patterns both of which include the new placed stone on the board it is a four-four prohibit.
(3) If after Black placing a stone on one intersection, there appears two Three patterns both of which include the new placed stone on the board it is a three-three prohibit.
If Black makes a prohibit-step WITHOUT making a Black Win pattern he(or she) will lose the game. (So White will win the game. )
Note: If Black makes a prohibit-step and at the same time he(or she) makes the Black Win pattern on the board he(or she) will WIN the game!

Input

There are several test cases.
In the first line, there is a positive integer N, which is the number of the test cases.
Then followed N test cases, in each test case, there are some lines. Each line contains two numbers: x and y (0<x<16,0<y<16) indicating the place where the stone will be placed. (Row number and Column number)
Ignore the input line if there is already a stone on the intersection. (Just like this line doesn't appear in the case)
Ignore the remaining input lines of a test case if Black or White has already win.
Each case is ended by a negative number.

Output

One line for each test case. If someone has won the game output the corresponding name of the winner (either Black or White),otherwise output "Draw" instead(without quotations).

Sample Input

3
9 9
8 6
9 8
8 5
9 7
7 2
9 6
3 4
9 5
-1
9 9
9 9
8 8
9 8
8 7
2 3
8 6
4 4
8 5
2 5
8 4
-1
1 1
15 15
-1
Sample Output

Black
White
Draw

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-05-12 15:51
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥50 树莓派安卓APK系统签名
  • ¥15 maple软件,用solve求反函数出现rootof,怎么办?
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥15 state显示变量是字符串形式,但是仍然红色,无法引用,并显示类型不匹配
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波