Как найти все возможные 5 точек в игре Join Five

Question

Я пытаюсь реализовать игру Join Five .Это игра, в которой, учитывая сетку и начальную конфигурацию точек, вы должны добавить точки в свободных точках пересечения, чтобы каждая добавляемая вами точка образовывала линию из 5 точек с уже имеющимися в сетке.Две линии могут иметь только одну общую точку (они могут пересекаться или касаться друг от друга)

Моя игровая сетка представляет собой массив int, который содержит 0 или 1. 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-точечные выравнивания, или сказать, есть ли лучший способ сделать это?

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;
}