Крыса в лабиринте Проблема, когда разрешено движение во всех возможных направлениях

// C ++ реализация вышеуказанного подхода
#include <bits/stdc++.h>
#define MAX 5

using namespace std;

  
// Функция возвращает true, если
// движение принято еще
// он вернет false.

bool isSafe(int row, int col, int m[][MAX], 

                 int n, bool visited[][MAX])

{

    if (row == -1 || row == n || col == -1 || 

                  col == n || visited[row][col] 

                           || m[row][col] == 0)

        return false;

    return true;

}

  
// Функция для печати всех возможных
// пути от (0, 0) до (n-1, n-1).

void printPathUtil(int row, int col, int m[][MAX], 

              int n, string& path, vector<string>& 

               possiblePaths, bool visited[][MAX])

{

    // Это проверит начальную точку

    // (т.е. (0, 0)), чтобы начать пути.

    if (row == -1 || row == n || col == -1 

               || col == n || visited[row][col] 

                           || m[row][col] == 0)

        return;

    // Если достигнуть последней ячейки (n-1, n-1)

    // затем сохраняем путь и возвращаем

    if (row == n - 1 && col == n - 1) {

        possiblePaths.push_back(path);

        return;

    }

    // Пометить ячейку как посещенную

    visited[row][col] = true;

    // Попробуйте все 4 направления (вниз, влево,

    // вправо, вверх) в указанном порядке, чтобы получить

    // пути в лексикографическом порядке

    // Проверка допустимости нисходящего движения

    if (isSafe(row + 1, col, m, n, visited))

    {

        path.push_back('D');

        printPathUtil(row + 1, col, m, n,

                 path, possiblePaths, visited);

        path.pop_back();

    }

    // Проверяем, действителен ли левый ход

    if (isSafe(row, col - 1, m, n, visited))

    {

        path.push_back('L');

        printPathUtil(row, col - 1, m, n,

                   path, possiblePaths, visited);

        path.pop_back();

    }

    // Проверка правильности правильного хода

    if (isSafe(row, col + 1, m, n, visited)) 

    {

        path.push_back('R');

        printPathUtil(row, col + 1, m, n,

                   path, possiblePaths, visited);

        path.pop_back();

    }

     // Проверяем, действителен ли верхний ход

    if (isSafe(row - 1, col, m, n, visited))

    {

        path.push_back('U');

        printPathUtil(row - 1, col, m, n,

               path, possiblePaths, visited);

        path.pop_back();

    }

    // Пометить ячейку как не посещенную для

    // другие возможные пути

    visited[row][col] = false;

}

  
// Функция для хранения и печати
// все действительные пути

void printPath(int m[MAX][MAX], int n)

{

    // вектор для хранения всех возможных путей

    vector<string> possiblePaths;

    string path;

    bool visited[n][MAX];

    memset(visited, false, sizeof(visited));

    // Вызов функции полезности для

    // найти правильные пути

    printPathUtil(0, 0, m, n, path, 

                      possiblePaths, visited);

    // Распечатать все возможные пути

    for (int i = 0; i < possiblePaths.size(); i++)

        cout << possiblePaths[i] << " ";

}

  
// Код драйвера

int main()

{

    int m[MAX][MAX] = { { 1, 0, 0, 0, 0 },

                        { 1, 1, 1, 1, 1 },

                        { 1, 1, 1, 0, 1 },

                        { 0, 0, 0, 0, 1 },

                        { 0, 0, 0, 0, 1 } };

    int n = sizeof(m) / sizeof(m[0]);

    printPath(m, n);

    return 0;

}