QOJ.ac

QOJ

حد الوقت: 1 s حد الذاكرة: 64 MB مجموع النقاط: 100

#2043. 构造序列

الإحصائيات

公司的下一个产品将是一款新游戏,它是经典游戏“井字棋”(Tic-Tac-Toe)的三维变体。两名玩家在三维空间(棋盘)中放置球,并试图连成特定长度的序列。

人们认为玩这个游戏很有趣,但他们仍然无法确定游戏的一些参数值。例如,多大的棋盘尺寸会让游戏最令人兴奋?目前正在讨论的参数是棋盘尺寸(下文称为 $n$)和序列长度($m$)。为了确定这些参数值,需要你编写一个游戏计算机模拟器。

你可以在图 3-5 中看到游戏的几个快照。这些图对应于样例输入中给出的三个数据集。

图 3:$n = m = 3$ 的游戏

以下是该游戏的精确规则。

  1. 两名玩家,黑方(Black)和白方(White),轮流下棋。黑方先手。
  2. 棋盘上有 $n \times n$ 个垂直立柱。每个立柱最多可容纳 $n$ 个球。立柱可以通过其 $x$ 和 $y$ 坐标($1 \le x, y \le n$)来指定。立柱上的球可以通过其 $z$ 坐标($1 \le z \le n$)来指定。游戏开始时,所有立柱上都没有球。

图 4:$n = m = 3$ 的游戏(白方在黑方之前连成了 3-序列)

  1. 在自己的回合中,玩家选择 $n \times n$ 个立柱中的一个,并将自己颜色的球放入该立柱。球遵循重力定律。也就是说,球会停在同一立柱上最顶端的球的正上方,或者停在底板上(如果该立柱上没有球)。换句话说,玩家可以选择球的 $x$ 和 $y$ 坐标,但不能选择其 $z$ 坐标。
  2. 游戏的目标是连成一个 $m$-序列。如果一名玩家连成了长度为 $m$ 或更长的同色球序列,他就获胜。$m$-序列是指 $m$ 个连续的同色球。例如,位于 $(5, 1, 2)$、$(5, 2, 2)$ 和 $(5, 3, 2)$ 的黑球构成了一个 3-序列。序列可以是水平、垂直或对角线的。准确地说,共有 13 种可能的序列方向,分类如下:

图 5:$n = 4, m = 3$ 的游戏(黑方连成了两个 4-序列)

(a) 一维轴向。例如,$(3, 1, 2)$、$(4, 1, 2)$ 和 $(5, 1, 2)$ 是一个 3-序列。此类方向共有三种。 (b) 二维对角线。例如,$(2, 3, 1)$、$(3, 3, 2)$ 和 $(4, 3, 3)$ 是一个 3-序列。此类方向共有六种。 (c) 三维对角线。例如,$(5, 1, 3)$、$(4, 2, 4)$ 和 $(3, 3, 5)$ 是一个 3-序列。此类方向共有四种。

注意,我们不区分相反的方向。

作为游戏评估过程的一部分,人们在改变参数值的情况下多次进行了游戏。你将获得这些游戏的记录。你的任务是编写一个计算机程序,确定每场记录游戏中的获胜者。

由于人类很难发现三维序列,玩家往往没有注意到游戏已经结束,并继续进行无意义的落子。在这种情况下,游戏结束(即获胜者确定)之后的落子应该被忽略。例如,在一名玩家通过连成 $m$-序列获胜后,玩家可能会连成额外的 $m$-序列。在这种情况下,除第一个 $m$-序列外,所有后续的 $m$-序列都应被忽略,且游戏的获胜者保持不变。

游戏不一定以其中一名玩家的胜利而结束。如果棋盘上没有剩余空间放置球,游戏以平局结束。此外,人们可能在连成任何 $m$-序列之前就退出游戏。在这种情况下,游戏也以平局结束。

输入格式

输入包含多个数据集,每个数据集对应一场游戏的记录。数据集的第一行包含三个正整数 $n$、$m$ 和 $p$,中间用空格分隔。它们满足关系 $3 \le m \le n \le 7$ 和 $1 \le p \le n^3$。$n$ 和 $m$ 是如上所述的游戏参数值,$p$ 是游戏中的落子次数。

数据集的其余部分包含 $p$ 行,每行包含两个正整数 $x$ 和 $y$。每一行描述一次落子,即当前玩家将球放入指定的立柱。你可以假设 $1 \le x \le n$ 且 $1 \le y \le n$。你还可以假设在整个游戏过程中,每个立柱上最多放置 $n$ 个球。

输入的结尾由一行包含三个零的行表示,中间用空格分隔。

输出格式

对于每个数据集,输出一行,描述获胜者和游戏结束时的落子次数。获胜者为“Black”或“White”。获胜者和落子次数之间应插入一个空格。输出中不允许包含其他多余字符。

如果是平局,输出行应为“Draw”。

样例

样例输入 1

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

样例输出 1

Draw
White 6
Black 15

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.