三维井字棋游戏说明

贵公司的下一个产品将是一款新游戏，它是经典游戏"Tic-Tac-Toe"的三维变体。两名玩家将球放在一个$n×n×n$的三维空间（棋盘）中，并尝试制作一个长度为$m$的序列。

游戏参数讨论

人们认为玩游戏很有趣，但他们仍然无法固定游戏的某些参数的值。例如：

• 棋盘尺寸（记作$n$）
• 序列长度（记作$m$）

为了确定这些参数值，您需要编写游戏的计算机模拟器。您可以在图3-5中看到游戏的几个快照。这些数字对应于Sample Input中给出的三个数据集。

游戏规则

黑队和白队两名玩家交替进行游戏。黑方先下。

1. 棋盘设置：

   • 有$n×n$个垂直钉子
   • 每个钉子最多可容纳$n$个球
   • 钉子坐标：$(x,y)$，其中$1≤x,y≤n$
   • 球坐标：$(x,y,z)$，其中$1≤z≤n$
   • 初始状态：任何钉子上都没有球

2. 游戏进行：

   • 玩家选择$(x,y)$位置放置球
   • 球遵循重力规则：自动落在该钉子现有球堆的顶部
   • 玩家只能选择$(x,y)$，不能选择$z$坐标

3. 胜利条件：

   • 制作一个$m$序列即获胜
   • $m$序列定义：$m$个同色球的连续排列
   • 示例：$(5,1,2)$,$(5,2,2)$,$(5,3,2)$的黑球形成3序列

序列方向分类

1. 一维轴（3个方向）：

   • 示例：$(3,1,2)$,$(4,1,2)$,$(5,1,2)$

2. 二维对角线（6个方向）：

   • 示例：$(2,3,1)$,$(3,3,2)$,$(4,3,3)$

3. 三维对角线（4个方向）：

   • 示例：$(5,1,3)$,$(4,2,4)$,$(3,3,5)$

注：不区分相反方向。

游戏结束条件

1. 正常结束：

   • 首个$m$序列出现时立即判定胜负
   • 后续移动将被忽略

2. 平局情况：

   • 所有钉子填满
   • 游戏提前终止

输入输出规范

输入格式

n m p
x₁ y₁
x₂ y₂
...
xₚ yₚ
0 0 0

参数范围：

• $3≤m≤n≤7$
• $1≤p≤n^3$
• $1≤x,y≤n$

输出格式

• 获胜：Black X或White X
• 平局：Draw

示例

输入示例

3 3 3
1 1
1 1
1 1
3 3 7
2 2
1 3
1 1
2 3
2 1
3 3
3 1
4 3 15
1 1
2 2
1 1
3 3
3 3
1 1
3 3
3 3
4 4
1 1
4 4
4 4
4 4
4 1
2 2
0 0 0

输出示例

Draw White 6 Black 15

来源

日本2004程序设计竞赛