Алгоритм решения лабиринта в C

Question

В основном, я пытаюсь реализовать алгоритм в C, который может решить лабиринт с использованием правого или левого правила. Я получаю треугольный лабиринт, как это в файле:

Я уже реализованы функции для разбора файла и загружать лабиринт в динамический 2D массива. Из значений в массиве я могу определить, имеет ли каждое поле или нет правую границу, левую границу и вертикальную границу (сверху или снизу, в зависимости от положения поля). Мне также сообщаются координаты начальной точки (т. Е. 6,1 в данном конкретном примере) и начальная граница (ниже), и, конечно же, следует ли использовать правую руку или правило левой руки, чтобы найти Выход.

Я должен указать координаты полей, которые ведут к выходу. Я в основном реализовал все необходимые функции для синтаксического анализа и проверки действительности лабиринта, но я не совсем понимаю, как поместить правое и левое правило в алгоритм. Надеюсь, этого достаточно, чтобы понять, что я пытаюсь сделать. Мне не обязательно нужен конкретный код, мне нужно только понять, как это сделать.

Спасибо.

Answer 1

Сформулируем правое правило в терминах треугольных ячеек лабиринта. Предположим, мы вошли в ячейку, пересекая ее нижний край, как показано серой стрелкой на диаграмме ниже.

Правого правило говорит нам, чтобы держать правую руку на стене. Когда мы вводим ячейку, где находится стена?

В первом случае сверху нет стены справа. Там должна быть стена где-то справа от нас, поэтому мы хотим продолжать поворачивать направо, пока мы не ударим ее. Поворот направо в треугольном лабиринте означает поворот на 60 градусов по часовой стрелке и переход по краю треугольника в соседнюю ячейку.

Во втором случае при входе в ячейку есть стена справа. Мы хотим сохранить эту стенку справа от нас, поэтому повернуть налево и перейти к соседней ячейке в этом направлении.

В третьем случае стены с обеих сторон. Мы должны развернуться и покинуть камеру. Мы возвращаемся в предыдущую ячейку, двигаясь в противоположном направлении, поэтому на этот раз стена справа будет другим краем треугольника.

Чтобы следовать левому правилу, мы используем аналогичные рассуждения на зеркальном изображении вышеприведенной иллюстрации.

Далее нам нужно числовое представление ячеек сетки. Существуют различные способы номера ячеек и ребер. Одна из возможностей показана на диаграмме ниже. Края каждого треугольника нумеруются 0, 1, 2. Слева - две ориентации треугольника, показывающие нумерацию ребер для каждого. В центре расположены восемь возможных настенных конфигураций для каждой ориентации треугольника. Справа - десятичные и двоичные представления каждой конфигурации стены, используя номер края для индексации двоичных цифр справа налево, , т. Е., от наименее значащей цифры до самой значащей цифры.

С этой схемой нумерации, лабиринты показано в этом вопросе может быть представлена ​​следующим текстом. Первая строка содержит количество строк и столбцов в сетке.Вторая строка описывает нашу начальную точку: номер строки, номер столбца, перекрестный край. Остальные строки содержат описания ячеек.

6 7 
6 1 2 
4 2 1 1 5 0 3 
4 1 2 0 2 0 1 
4 0 1 0 1 3 4 
4 2 7 4 0 1 1 
6 4 1 1 6 4 2 
2 2 6 0 2 2 6 

Заключительная часть реализации является переходной матрицей, которая позволяет нам смотреть на следующее состоянии в лабиринте обходе данного текущее состояние и края мы пересечение.

Прежде чем описывать матрицу перехода, позвольте мне четко сказать, как мы нумеруем сетку. Внешне мы будем указывать строки и столбцы, начиная с единицы, как показано на диаграмме. Вот как мы будем читать начальное местоположение, и именно так мы будем отображать решение для пользователя. Однако в рамках программы удобно указывать строки и столбцы, начиная с нуля, потому что это то, как индексирует массивы языка C. Например, мы скажем, что верхняя левая ячейка находится в строке 0 и в столбце 0. Это означает, что если у нас есть двумерный целочисленный массив, называемый maze, мы будем ссылаться на верхнюю левую ячейку как maze[0][0].

Учитывая индекс строки и столбца r индекс c треугольной ячейки сетки, используя нумерацию с нуля, давайте выяснять ориентацию треугольника с соотношением r и c. Если они имеют одинаковую четность, то есть они оба нечетные или оба четные, треугольник указывает вниз. В противном случае он указывает вверх. Простым способом реализации этого является вычисление (r+c)%2, которое равно 0, если четности совпадают и 1, если четности различаются.

Далее мы должны принять во внимание край, который мы пересекаем. Если мы знаем, ориентацию треугольника мы уезжаем, и число края, что мы пересекающий, мы можем работать:

• Номер строки треугольника, мы входим.

• Номер столбца треугольника, который мы вводим.

• Номер края, который мы пересекли, в контексте вновь введенного треугольника.

Вся эта информация представлена ​​в следующем трехмерном массиве.

moves[2][3][3] = { 
     { {-1, 0, 1}, {0, 1, 2}, {0, -1, 0} }, 
     { {0, 1, 2}, {1, 0, 0}, {0, -1, 1} } }; 

Первый индекс для ориентации треугольника с 0 для нисходящего треугольника и 1 для восходящего треугольника. Второй индекс - это номер края, который мы пересекаем, используя нумерацию границ треугольника, который мы оставляем. Третий индекс используется для поиска трех частей информации, перечисленных выше.

• 0: Изменение номера строки.

• 1: Изменение номера столбца.

• 2: Номер края, который мы только что пересекли, используя нумерацию края нового треугольника.

Например, давайте посмотрим на первый шаг в лабиринте образца. Мы начинаем в строке 5, колонка 0.Суммарная четность равна 1, что означает восходящий треугольник. Мы пересекаем край 0. Таким образом, мы смотрим на maze[1][0]. Полученная информация {0, 1, 2}, говорит нам, что в новой ячейке:

• рядного изменения индекса от 0.

• Индекс колонок изменяется на 1.

• Мы только что пересекли границу 2.

Теперь мы можем применить алгоритм в цикле, который заканчивается после того, как мы покинули границы лабиринта.

Ниже приведена реализация ANSI C концепций, которые я обсуждал. Вам придется адаптировать его к любому файловому формату, который вы используете для представления лабиринта. Помните, что в описании исходного местоположения в моем формате указан край, который был пересечен для входа в лабиринт.

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

int **maze, row_num, col_num, 
    moves[2][3][3] = { /* moves[orientation][edge] == {dr, dc, crossed} */ 
     { {-1, 0, 1}, {0, 1, 2}, {0, -1, 0} }, 
     { {0, 1, 2}, {1, 0, 0}, {0, -1, 1} } }; 

void go(int r, int c, int crossed, int turn) { 
    int edge, *move; 
    while (1) { 
    if (r < 0 || r >= row_num || c < 0 || c >= col_num) { 
     printf("out\n\n"); /* We've left the maze. */ 
     return; 
    }     /* Increment the indices for external display. */ 
    printf("%d %d\n", r+1, c+1); 
    edge = crossed;  /* We'll consider the crossed edge last. */ 
    while (1) {   /* Turn and look for an open edge. */ 
     edge = (edge+turn+3)%3; 
     if ((maze[r][c] & (1 << edge)) == 0) { 
     break; 
     } 
    } 
    move = moves[(r+c)%2][edge]; 
    r += move[0];  /* After looking up the move, update the */ 
    c += move[1];  /* cell position and the edge number. */ 
    crossed = move[2]; 
    } 
} 

int main() { 
    int r_start, c_start, crossed_start, r, c; 
    scanf("%d %d", &row_num, &col_num); 
    scanf("%d %d %d", &r_start, &c_start, &crossed_start); 
    --r_start;    /* We decrement the cell indices because */ 
    --c_start;    /* they are zero-based internally. */ 
    maze = (int **) malloc(row_num*sizeof(int *)); 
    for (r = 0; r < row_num; ++r) { 
    maze[r] = (int *) malloc(col_num*sizeof(int)); 
    for (c = 0; c < col_num; ++c) { 
     scanf("%d", &maze[r][c]); 
    } 
    } 
    printf("\nRight-hand rule:\n"); 
    go(r_start, c_start, crossed_start, -1); 
    printf("Left-hand rule:\n"); 
    go(r_start, c_start, crossed_start, 1); 
    return 0; 
}