algorithm - 如何找到修改后的黑白棋/黑白棋游戏的赢家？

Question

我在另一个网站上看到这个面试问题。

在奥赛罗游戏中，红色或黑色圆盘按照特定规则放置在 8x8 网格上。玩家选择自己的颜色，网格上拥有最多圆盘数的玩家获胜。

给定两个二维数组(一个代表红色，另一个代表黑色)表示磁盘的存在/不存在，以及以下规则:

• 对于长度为 n > 3 的序列，分配 (n-2) 作为该玩家的点数
• 序列可以是垂直的、水平的或对角线的
• 一个盘不能属于多个序列

例如对于下面的二维数组，点将是对角线元素(包括[0,0])和第一行元素(不包括[0,0])的最大值，或者对角线元素(不包括[0， 0])和水平元素(包括[0,0])。即 max(4+0, 3+2) = 5

1 1 1 1 0 0
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1

根据最高分确定获胜者。

Answer 1

我有一个建议，尽管您可能会找到一个更简单的建议。

要计算玩家的分数，请分配一个 8X8 二维结构数组，其中包含以下字段:垂直、水平、对角线 1、对角线 2。

在算法执行结束时，这四个字段将保存“到目前为止”序列的大小 - 例如，如果此单元格中有圆盘，则单元格 (x,y) 的“垂直”字段将保存 1 ，并且在(x，y-1)处没有圆盘，如果在(x，y)和(x，y-1)处有圆盘但在(x，y-2)处没有圆盘则为2等。相同关于其他3个领域。您还需要一个 score 变量，以对所获得的分数求和。

现在你应该按升序逐行浏览这个数组，从 (0,0) 单元格开始 [(0,0),(0,1)....(0,7),(1 ,0)...] 并填充结构。在每个单元格中，您首先检查原始二维阵列的等效单元格中是否有圆盘。如果没有圆盘，你应该保留分数，并将当前单元格的结构的所有字段设置为0。如果有圆盘(假设当前单元格是(x，y))，你应该分配如下:

(x,y)->vertical = (x,y-1)->vertical,
(x,y)->horizontal = (x-1,y)->horizontal,
(x,y)->diagonal1 = (x-1,y-1)->diagonal1,
(x,y)->diagonal2 = (x+1,y-1)->diagonal2.

请注意，在每个点上，您需要的所有值都已计算完毕。如果超出范围(x-1 < 0 等)，该值为 0。您还应该为每个分配 4 的字段增加 2 或为每个分配 5 或更多的字段增加 1(这将为每个长度为 n > 3 的序列提供 n-2 分)。

就是这样。在遍历所有 2D 数组后，得分计数器将保存玩家的得分。

复杂度为O(n^2)，一点都不差(实际上你在复杂度上找不到更好的解决方案)。