2

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

在奥赛罗游戏中，红色或黑色圆盘按照一定的规则放置在 8x8 格子上。玩家选择他们的颜色，并且在网格上拥有最大数量的磁盘的玩家获胜。

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

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

例如，对于下面的二维数组，点将是对角元素（包括 [0,0]）和第一行中的元素（不包括 [0,0]）的最大值，或者是对角元素（不包括 [0 ,0]）和水平元素（包括[0,0]）。即最大(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

以最高分确定获胜者。

4

2 回答 2

0

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

要计算玩家的分数，请分配一个 8X8 2D 结构数组，其中包含以下字段：垂直、水平、对角线 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 个点）。

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

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

于 2012-04-15T00:17:06.210 回答
0

要了解规则，请尝试此链接www.springfrog.com/games/othello/othello.htm

使用的数据结构：

板：int[8][8]；

uncounted_red：2，uncounted_black：-2，空：0；

counted_red：1，counted_black：-1

score_red：int， score_black：int；

算法：

  1. 查找长度 > 3 的连续红色序列

  2. 对于找到的每个序列，添加分数长度 - 2

  3. 通过在序列中遇到的已经计数的钉子进一步降低分数。

  4. 计算完分数后，所有未计数的钉子都已计数。

  5. 对黑色重复该过程。

  6. 获胜者 = score_red > score_black ？红黑。

现在问题归结为如何执行第 1 步。

于 2012-07-27T02:47:21.793 回答