Рубрики

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

Рассмотрим крысу, помещенную в точке (0, 0) в квадратной матрице m [] [] порядка n, и она должна достичь пункта назначения в (n-1, n-1) . Задача состоит в том, чтобы найти отсортированный массив строк, обозначающий все возможные направления, по которым крыса может добраться до пункта назначения (n-1, n-1) . Направления, в которых может двигаться крыса: «U» (вверх), «D» (вниз), «L» (слева), «R» (справа).

Примеры:

Input : N = 4
1 0 0 0
1 1 0 1
0 1 0 0
0 1 1 1
Output :
DRDDRR
On following the path DRDDRR ,the rat can reach the bottom right of the maze.

Input :N = 4
1 0 0 0
1 1 0 1
1 1 0 0
0 1 1 1
Output :
DDRDRR DRDDRR

Подходить:

  • Начните с начального индекса (т. Е. (0,0)) и найдите действительные перемещения через соседние ячейки в порядке Вниз- Влево-> Вправо-> Вверх (чтобы получить отсортированные пути) в сетке.
  • Если перемещение возможно, то перемещайтесь в эту ячейку, сохраняя символ, соответствующий ходу (D, L, R, U), и снова начинайте искать действительный ход до последнего индекса (то есть (n-1, n-1). )) достигнуто.
  • Кроме того, продолжайте отмечать ячейки как посещенные, и когда мы пройдем все возможные пути из этой ячейки, затем снимите отметку с этой ячейки для других различных путей и удалите символ из сформированного пути.
  • Когда будет достигнут последний индекс сетки (внизу справа), сохраните пройденный путь.

Ниже приведена реализация вышеуказанного подхода

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

}

Выход:

DDRRURRDDD DDRURRRDDD DRDRURRDDD DRRRRDDD

Рекомендуемые посты:

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

0.00 (0%) 0 votes