Поиск пути в лабиринте. Рекурсивный метод

Автор — Панфилов Александр, преподаватель

Постановка задачи. Для любого заданного лабиринта определить путь (не обязательно кратчайший) от стартовой клетки до целевой клетки, например:


Замечание. Данную задачу можно решить в итеративном (не рекурсивном) виде, но в рекурсивном виде она получается понятнее и компактнее.

Алгоритм поиска пути в лабиринте

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

Исключение хода в направление, из которого попадаем в текущую клетку, необходимо, чтобы алгоритм поиска пути не зациклился.
Применяя это правило рекурсивно к каждой клетке, в которую попадаем, мы гарантируем, что будет найден путь до цели, но необязательно кратчайший.
Чтобы составить рекурсивный алгоритм надо определиться с простейшим случаем, т.е. завершением функции без рекурсии. Такой случай – текущая клетка является целевой.

Словесный алгоритм работы будет такой:
Если текущая клетка = целевая, то завершить поиск с успехом (true).
Для очередной клетки повернуть в каждое доступное направление, кроме того, откуда пришли в эту клетку, т.е.:
пойти налево, если это возможно И пришли не справа. Если путь успешен – завершить поиск;
пойти направо, если это возможно И пришли не слева. Если путь успешен – завершить поиск;
пойти вверх, если это возможно И пришли не снизу. Если путь успешен – завершить поиск;
пойти вниз, если это возможно И пришли не сверху. Если путь успешен – завершить поиск;
Завершить поиск с неуспехом (false).

Для учета направления, из которого попадаем в очередную клетку, используем тип-перечисление:
enum Dir { Left, Right, Up, Down, None }
Значение «None» пригодится для стартовой клетки, т.к. в нее мы ниоткуда не попадаем.

Представление лабиринта

Поле лабиринта можно представить в виде матрицы (двумерного массива), каждый элемент которой представлял бы информацию, какие направления в ней свободны, является ли она стартовой или целевой.
Для этого можно определить новый класс «Клетка», а можно использовать более компактное, в плане расхода памяти, решение – закодировать всю необходимую информацию в виде числа.
Итак, пусть «Клетка» = число, размером в 1 байт. Каждый отдельный бит этого числа будет иметь свой смысл (см. рисунок):
— 0-й бит – свободно ли направление «налево», 1 = можно пройти, 0 = стена;
— 1-й бит – свободно ли направление «вверх», 1 = можно пройти, 0 = стена;
— 2-й бит – свободно ли направление «направо», 1 = можно пройти, 0 = стена;
— 3-й бит – свободно ли направление «вниз», 1 = можно пройти, 0 = стена;
— 4-й бит – является ли клетка стартовой;
— 5-й бит – является ли клетка целевой.

Таким образом, двоичное значение клетки 00001010 (или десятичное 10) будет означать, что у клетки свободны направления «низ» и «верх», а «справа» и «слева» — находятся стены.
С учетом такого кодирования клеток, лабиринт будет соответствовать числовой матрице:

Для кодирования клеток используем тип-перечисление:

//коды для клетки лабиринта
enum Code : byte
{
  Left = 1,
  Up = 2,
  Right = 4,
  Down = 8,
  Start = 16,
  Finish = 32
}

Весь лабиринт будет описываться как матрица элементов типа Code:

Code[,] labirint;

Удобство такого кодирования ячеек еще и в том, что становится просто проверить «свободность» выбранного направления у заданной клетки. Для этого надо проверить наличие двоичной 1 в соответствующем бите. Это можно сделать операцией «побитового И» — &.
Например, проверка, что у клетки свободно направление «вверх» запишется так:

if ((labirint[row, col] & Code.Up) != 0) ...

Загрузка лабиринта из файла

Для тестирования программы вводить вручную матрицу лабиринта в консоли неудобно. Лучше предусмотреть возможность хранения и загрузки матрицы лабиринта из файла. Для удобства представления и редактирования выберем текстовый формат файла со следующей структурой:
— в 1-й строке файла хранятся два числа, разделенных пробелом – число строк и столбцов матрицы лабиринта;
— начиная со 2-й строки – построчные значения матрицы лабиринта, разделенные пробелом.
Для лабиринта, указанного выше, текстовый файл будет иметь такой вид:

Метода загрузки матрицы лабиринта – LoadLabirint(), приведен в коде ниже.

Полный программный код

using System;
using System.IO; //для работы с файлом (загрузка матрицы лабиринта из файла)
namespace Recursive
{
    class Program
    {
        static void Main(string[] args)
        {
            Code[,] labirint = LoadLabirint(); //загрузить лабиринт
            bool reached = RecPoisk(labirint, 7, 2, Dir.None);
            Console.WriteLine("\n\nНайден путь: " + reached);
        }

        // Поиск с клетки [row, col] с учетом того, что пришли в нее с направления dir.
//  Возвращаемый результат – удачен ли поиск пути из текущей клетки [row, col]
        private static bool RecPoisk(Code[,] labirint, int row, int col, Dir dir)
        {
            if ((labirint[row, col] & Code.Finish) != 0) //целевая клетка?
            {
                Console.Write($"[{row},{col}]");
                return true;
            }

            bool reached = false;
            //если налево свободно И пришел НЕ справа
            if ((labirint[row, col] & Code.Left) != 0 && dir != Dir.Right)
                reached = RecPoisk(labirint, row, col - 1, Dir.Left);
            //если направо свободно И пришел НЕ слева
            if (!reached && (labirint[row, col] & Code.Right) != 0 && dir != Dir.Left)
                reached = RecPoisk(labirint, row, col + 1, Dir.Right);
            //если наверх свободно И пришел НЕ снизу
            if (!reached && (labirint[row, col] & Code.Up) != 0 && dir != Dir.Down)
                reached = RecPoisk(labirint, row - 1, col, Dir.Up);
            //если вниз свободно И пришел НЕ сверху
            if (!reached && (labirint[row, col] & Code.Down) != 0 && dir != Dir.Up)
                reached = RecPoisk(labirint, row + 1, col, Dir.Down);
            if(reached)
                Console.Write($"<-[{row},{col}]");
            return reached;
        }

        //загрузить лабиринт из текстового файла
        private static Code[,] LoadLabirint()
        {
            Code[,] lab = null;
            using (StreamReader f = new StreamReader("labirint.txt"))
            {
                string[] delim = new string[] { " " };
                string str = f.ReadLine();
                string[] mas = str.Split(delim, StringSplitOptions.RemoveEmptyEntries);
                int row = int.Parse(mas[0]);
                int col = int.Parse(mas[1]);
                lab = new Code[row, col];
                int i = 0;
                while ((str = f.ReadLine()) != null)
                {
                    mas = str.Split(delim, StringSplitOptions.RemoveEmptyEntries);
                    for (int j = 0; j < col; j++)
                        lab[i, j] = (Code)int.Parse(mas[j]);
                    i++;
                }
            }
            return lab;
        }
    }

    //направление с которого пришли в клетку
    enum Dir { Left, Right, Up, Down, None }

    //коды клетки лабиринта
    enum Code : byte
    {
        Left = 1,
        Up = 2,
        Right = 4,
        Down = 8,
        Start = 16,
        Finish = 32
    }
}

Пример работы программы:

Видно, что найденный путь из стартовой клетки [7,2] до целевой [7,7] выводится в обратном порядке.

Чтобы проследить порядок вызовов рекурсивной функции можно в метод RecPoisk добавить дополнительные строки вывода на консоль (помечены /**/ в коде ниже).

        private static bool RecPoisk(Code[,] labirint, int row, int col, Dir dir)
        {
/**/      Console.Write($"row={row}, col={col}, cell={labirint[row, col]}, dir={dir}");
/**/      Console.ReadKey();
            if ((labirint[row, col] & Code.Finish) != 0)
            {
                Console.Write($"[{row},{col}]");
                return true;
            }

            bool reached = false;
            //если налево свободно И пришел НЕ справа
            if ((labirint[row, col] & Code.Left) != 0 && dir != Dir.Right)
            {
/**/          Console.WriteLine(" -> Left");
                reached = RecPoisk(labirint, row, col - 1, Dir.Left);
            }
            //если направо свободно И пришел НЕ слева
            if (!reached && (labirint[row, col] & Code.Right) != 0 && dir != Dir.Left)
            {
/**/          Console.WriteLine(" -> Right");
                reached = RecPoisk(labirint, row, col + 1, Dir.Right);
            }
            //если наверх свободно И пришел НЕ снизу
            if (!reached && (labirint[row, col] & Code.Up) != 0 && dir != Dir.Down)
            {
/**/          Console.WriteLine(" -> Up");
                reached = RecPoisk(labirint, row - 1, col, Dir.Up);
            }
            //если вниз свободно И пришел НЕ сверху
            if (!reached && (labirint[row, col] & Code.Down) != 0 && dir != Dir.Up)
            {
/**/          Console.WriteLine(" -> Down");
                reached = RecPoisk(labirint, row + 1, col, Dir.Down);
            }
            if(reached)
                Console.Write($"<-[{row},{col}]"); /**/ Console.Write($"[{row},{col}] -> none");
            return reached;
        }

Задания на самостоятельную работу

1) Измените в методе RecPoisk() порядок проверки направления в текущей клетки с «лево, право, верх, низ» на «лево, низ, право, верх». Будет ли находиться путь в лабиринте в этом случае?
2) Стартовая ячейка в методе Main задана явно:
bool reached = RecPoisk(labirint, 7, 2, Dir.None);
Напишите метод для определения строки и столбца со стартовой клеткой.
3) Протокол вывода пути в лабиринте выводится в «обратном» виде, от целевой клетки к начальной. Как обеспечить вывод пути в «прямом» направлении, от начальной клетки у целевой?

---

NEW: Наш Чат, в котором вы можете обсудить любые вопросы, идеи, поделиться опытом или связаться с администраторами.

---

Помощь проекту: