c - 如何在 Join Five 游戏中找到所有可能的 5 点对齐

Question

我正在尝试实现 Join Five游戏。在这个游戏中，给定一个网格和点的起始配置，您必须在自由交叉点添加点，以便您添加的每个点与网格中已有的点形成一条 5 点线。两条线可能只有 1 个共同点(它们可能交叉或首尾相连)

我的游戏网格是一个包含 0 或 1 的 int 数组。如果有一个点则为 1，如果没有则为 0。

我在实现方面做得还不错，但我想展示所有可能的 Action 。我做了一个又长又丑的函数，可以在这里找到:https://pastebin.com/tw9RdNgi (对不起，我的帖子太长了)这是一个代码片段:

if(jeu->plat[i][j] == 0) // if we're on a empty spot
            {
                for(k = 0; k < lineSize; k++) // for each direction
                {
                    //NORTH    
                    if(jeu->plat[i-1-k][j] == 1) // if there is a dot north 
                    {
                        n++; // we count it 
                    }
                    else
                    {
                        break; //we change direction
                    }
                } //  

这段代码会重复自身 7 次改变方向，如果 n 或任何其他变量达到 4，我们将 x 和 y 计算为可能的移动。

它甚至没有处理所有情况，如果可用点在 2 到 2 个点之间，它就不会计算在内。 3 和 1 以及 1 和 3 也一样。

但我不认为我开始做这件事的方式是最好的。我很确定有一种更简单、更优化的方法，但我想不出来。

所以我的问题是:有人可以帮我弄清楚如何找到所有可能的 5 点对齐方式，或者告诉我是否有更好的方法吗？

Answer 1

好吧，这个问题比看起来更难，需要大量的代码。如果您发布所有必要的代码来运行它，一切都会变得更简单，即 Minimal, Complete, and Verifiable Example .无论如何，我求助于将问题的结构放在一起，以便对其进行测试。

回答您问题的文章如下:

typedef struct board {
    int side_;
    char **dots_;
} board;

void board_set_possible_moves(board *b)
{
    /* Directions
        012
        7 3
        654 */
    static int dr[8] = { -1,-1,-1, 0, 1, 1, 1, 0 };
    static int dc[8] = { -1, 0, 1, 1, 1, 0,-1,-1 };

    int side_ = b->side_;
    char **dots_ = b->dots_;
    for (int r = 0; r < side_; ++r) {
        for (int c = 0; c < side_; ++c) {
            // The place already has a dot
            if (dots_[r][c] == 1)
                continue;
            // Count up to 4 dots in the 8 directions from current position
            int ndots[8] = { 0 };
            for (int d = 0; d < 8; ++d) {
                for (int i = 1; i <= 4; ++i) {
                    int nr = r + dr[d] * i;
                    int nc = c + dc[d] * i;
                    if (nr < 0 || nc < 0 || nr >= side_ || nc >= side_ || dots_[nr][nc] != 1)
                        break;
                    ++ndots[d];                        
                }
            }
            // Decide if the position is a valid one
            for (int d = 0; d < 4; ++d) {
                if (ndots[d] + ndots[d + 4] >= 4)
                    dots_[r][c] = 2;
            }
        }
    }
}

请注意，我定义了一个带有指向字符指针的方形板，每个位置一个。如果其中一个位置是 0，则没有点，该位置不是有效着法；如果有 1，则有一个点；如果有 2，则该位置没有点，但它是有效着法。此处有效表示至少有 4 个点与当前点对齐。您可以使用 0 到 7 之间的数字对方向进行建模(从 NW 开始，顺时针移动)。每个方向都有一个关联的运动，表示为 dr 和 dc。在每个方向上移动，我计算那里有多少个点(最多 4 个，一找到非点就停止)，然后我可以对相反的方向求和以获得对齐点的总数。

当然这些移动不一定有效，因为我们缺少已经绘制的线的定义，所以我们无法检查它们。

在这里您可以找到该功能的测试。

#include <stdio.h>
#include <stdlib.h>

board *board_init(board *b, int side) {
    b->side_ = side;
    b->dots_ = malloc(side * sizeof(char*));
    b->dots_[0] = calloc(side*side, 1);
    for (int r = 1; r < side; ++r) {
        b->dots_[r] = b->dots_[r - 1] + side;
    }
    return b;
}
board *board_free(board *b) {
    free(b->dots_[0]);
    free(b->dots_);
    return b;
}
void board_cross(board *b) {
    board_init(b, 18);
    for (int i = 0; i < 4; ++i) {
        b->dots_[4][7 + i] = 1;
        b->dots_[7][4 + i] = 1;
        b->dots_[7][10 + i] = 1;
        b->dots_[10][4 + i] = 1;
        b->dots_[10][10 + i] = 1;
        b->dots_[13][7 + i] = 1;

        b->dots_[4 + i][7] = 1;
        b->dots_[4 + i][10] = 1;
        b->dots_[7 + i][4] = 1;
        b->dots_[7 + i][13] = 1;
        b->dots_[10 + i][7] = 1;
        b->dots_[10 + i][10] = 1;
    }
}
void board_print(const board *b, FILE *f)
{
    int side_ = b->side_;
    char **dots_ = b->dots_;
    for (int r = 0; r < side_; ++r) {
        for (int c = 0; c < side_; ++c) {
            static char map[] = " oX";
            fprintf(f, "%c%s", map[dots_[r][c]], c == side_ - 1 ? "" : " - ");
        }
        fprintf(f, "\n");
        if (r < side_ - 1) {
            for (int c = 0; c < side_; ++c) {
                fprintf(f, "|%s", c == side_ - 1 ? "" : "   ");
            }
            fprintf(f, "\n");
        }
    }
}

int main(void)
{
    board b;
    board_cross(&b);

    board_set_possible_moves(&b);
    board_print(&b, stdout);

    board_free(&b);
    return 0;
}