0

我正在尝试实现加入五人 游戏。这是一个游戏，在给定网格和点的起始配置的情况下，您必须在自由交叉点中添加点，以便您添加的每个点与网格中已经存在的点形成一条 5 点线。两条线可能只有 1 个共同点（它们可能首尾相交或接触）

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

我在实施中做得很好，但我想展示所有可能的动作。我制作了一个非常长且丑陋的功能，可在此处获得：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 点对齐方式，或者告诉我是否有更好的方法吗？

4

1 回答 1

2

好的，问题比看起来要难，而且需要很多代码。如果您发布所有必要的代码来运行它，一切都会变得更简单，即最小、完整和可验证的示例。无论如何，我为这个问题拼凑了一个结构，可以对其进行测试。

回答您问题的部分如下：

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;
}
于 2019-04-12T22:45:03.147 回答