javascript - 在javascript中连接4算法

Question

在 connect 4 中连续检查 4 个的最佳方法是什么？

我不会复制数组的代码，但它基本上是一个长度为 42 的数组。每个数组元素包含用于绘制的 X、Y 位置和颜色

var board_array = [{x:60, y:55, c:"Red"}, // ... and so on

看起来像这样:

最初我采用了这种方法。以下是某人赢得比赛的所有不同可能方式。这不是所有可能的 4 个连续位置，而是某人可以垂直、水平和垂直获胜的所有不同方式 - 您仍然需要使用某种嵌套 for 循环进行检查

// Winning vertically
wins[0]  = new Array(0, 7,  14, 21, 28, 35);
wins[1]  = new Array(1, 8,  15, 22, 29, 36);
wins[2]  = new Array(2, 9,  16, 23, 30, 37);
wins[3]  = new Array(3, 10, 17, 24, 31, 38);
wins[4]  = new Array(4, 11, 18, 25, 32, 39);
wins[5]  = new Array(5, 12, 19, 26, 33, 40);
wins[6]  = new Array(6, 13, 20, 27, 34, 41);
// Winning horizontally
wins[7]  = new Array(0,   1,  2,  3,  4,  5,  6);
wins[8]  = new Array(7,   8,  9, 10, 11, 12, 13);
wins[9]  = new Array(14, 15, 16, 17, 18, 19, 20);
wins[10] = new Array(21, 22, 23, 24, 25, 26, 27);
wins[11] = new Array(28, 29, 30, 31, 32, 33, 34);
wins[12] = new Array(35, 36, 37, 38, 39, 40, 41);
// Winning diagonally, left to right
wins[13] = new Array(14, 22, 30, 38);
wins[14] = new Array(7, 15, 23, 31, 39);
wins[15] = new Array(0, 8, 16, 24, 32, 40);
wins[16] = new Array(1, 9, 17, 25, 33, 41);
wins[17] = new Array(2, 10, 18, 26, 34);
wins[18] = new Array(3, 11, 19, 27);
//Winning diagonally, right to left
wins[19] = new Array(20, 26, 32, 38);
wins[20] = new Array(13, 19, 25, 31, 37);
wins[21] = new Array(6,  12, 18, 24, 30, 36);
wins[22] = new Array(5,  11, 17, 23, 29, 35);
wins[23] = new Array(4,  10, 16, 22, 28);
wins[24] = new Array(3,   9, 15, 21);

如果你认为 board_array 是这样的:

//0  1  2  3  4  5  6
//7  8  9  10 11 12 13
//14 15 16 17 18 19 20
//21 22 23 24 25 26 27
//28 29 30 31 32 33 34
//35 36 37 38 39 40 41

我使用了一个 3 层 for 循环和一个计数器来检查 wins 数组与 board_array 的对比，但无济于事。我只是想知道是否有更简单的方法。

Answer 1

有很多方法可以做到这一点。如果你想摆脱循环，你可以使用动态编程算法，并在每次添加硬币时计算结果。

为此，您必须为每个字段保存 4 个值:水平、垂直、对 Angular 线左值和对 Angular 线右值

class Field {
       int horiz;
       int vert;
       int diagLeft;
       int diagRight;
}

一开始，所有字段都初始化为0(字段的所有值)。 如果将硬币添加到 Field，则可以这样计算值:

fields[i][j].horiz = fields[i][j+1].horiz + fields[i][j-1].horiz + 1;
fields[i][j].vert = fields[i+1][j].vert + fields[i-1][j].vert + 1;
fields[i][j].diagLeft = fields[i+1][j+1].diagLeft + fields[i-1][j-1].diagLeft +1;
fields[i][j].diagRight = fields[i-1][j-1].diagRight + fields[i+1][j+1]

如果四个计算值中的一个大于等于 4，则您获胜。

要处理两个玩家，您可以为每个玩家制作一个字段数组，或者您可以使用正值和负值

如果你想避免一直检查边界(i 和 j)，你可以在你的字段中添加一个边框(这样你就可以在左边和右边多出一列，在顶部和底部多出一行)