C++ 遍历 2D vector 以连续查找 3

Question

大家好，正在开发一款 C++ 小游戏“Connect 3”。这就像 Connect 4 , 除了我们只需要 3 场比赛就可以赢得比赛。我将我的电路板存储在一个包含整数的 2D vector 中。

vector< vector<int> > vector2d;

我将“X”存储为 1，将“O”存储为 -1，其中 0 为空白。到目前为止它似乎在工作。

因此，在我与计算机对弈的算法中，它会找到可能的最佳着法。我已经完成了算法，但它需要知道什么时候达到了“基本情况”。 (它是递归的。)基本情况是:

1. 某人连续获得 3 个，或者
2. 董事会已满

检查板是否已满很容易。我只是遍历并查看是否有任何空格是“0”。如果是，则板未满。但在我检查之前，我需要看看是否有人连续获得 3 个，这就是我遇到问题的地方。我能想到的唯一方法是大而复杂，3 次不同地遍历棋盘，寻找 3 的水平匹配、3 的垂直匹配和 3 的对角线匹配。我什至不确定从哪里开始这样做，我希望有更好的方法来做到这一点。非常感谢您的帮助!

此外，不确定是否允许我使用 Boost，到目前为止我还没有使用过，我希望不必使用它。 (不确定学校计算机是否有)。

编辑: 棋盘不必是 3 x 3。它可以是 1 x 7、7 x 7 或任何尺寸。如果它不是合法大小 (0,0)，我的代码会告诉用户，但任何其他板都应该可以工作。我使用 vector 大小来查看电路板有多大。

Answer 1

您不必每次都检查整个棋盘。只有新片才有所不同，因此您只需检查包含新片的那些结束条件。有 8 个不同的方向需要检查，但每两个方向都在同一条线上，应该一起检查。方向可以定义为 (delta_X, delta_Y) 对:(1,0),(0,1),(1,1),(1,-1)。您的代码应该在每个方向上遍历(如 Leonid 的代码)并尝试计算与新 block 具有相同值的 block 数。然后它应该从当前方向以 (-x,-y) 的相反方向遍历，并计算这些碎片。如果计数的件数为 N-1(新件已被计数)，则您获胜。