Вариант "Крысы в лабиринте": разрешено несколько шагов или прыжков.
Разновидность крысы в лабиринте.
Вам предоставлен лабиринт в форме двумерной матрицы размером N * N (назовем его M), в верхней левой ячейке есть крыса, то есть M [0] [0], а в нижней правой ячейке есть выход. т.е. M [N-1] [N-1] . Из каждой ячейки M [i] [j] (0 ≤ i ≤ N-1, 0 ≤ j ≤ N-1) крыса может пройти несколько шагов вправо (например, до M [i] [j + s ]) или количество шагов вниз (например: до M [i + s] [j]), где максимальное количество шагов (или максимальное значение s) может быть значением в ячейке M [i] [j ] . Если какая-либо ячейка содержит 0, то это тупик . Например: На втором изображении на рисунке ниже крыса в M [0] [0] может прыгнуть в ячейку: M [0] [1] , M [0] [2] , M [1] [0] ] или M [2] [0] .
Вы должны напечатать возможный путь от M [0] [0] до M [N-1] [N-1] в виде матрицы размера N * N , чтобы ячейки, находящиеся в пути, имели значение 1, а остальные ячейки имеют значение 0 . Для приведенного выше примера одно из таких решений:
В этой статье есть решение для этой проблемы с возвратом.
Здесь представлено решение на основе динамического программирования.
Примеры:
Input: mat[][] = {
{3, 0, 0, 2, 1},
{0, 0, 0, 0, 2},
{0, 1, 0, 1, 0},
{1, 0, 0, 1, 1},
{3, 0, 0, 1, 1} }
Output:
1 0 0 1 1
0 0 0 0 1
0 0 0 0 0
0 0 0 0 1
0 0 0 0 1Input: mat[][] = { {0, 0}, {0, 1} }
Output: No path exists
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Подход:
- Инициализируйте логическую матрицу CRF [N] [N] (может достигнуть) с ложью . Теперь установите CRF [N - 1] [N - 1] = true, поскольку пункт назначения может быть достигнут из пункта назначения.
- Теперь, начиная с лабиринта [N - 1] [N - 1] и заканчивая лабиринтом [0] [0], обновите все ячейки в CRF [] [] в зависимости от того, возможно ли достичь любой другой допустимой ячейки (ведущей к назначение).
- Когда вся матрица CRF [] [] обновлена, используйте для создания матрицы, которая содержит все единицы в ячейках пути, ведущего к месту назначения, а другие ячейки - нули .
- Напечатайте эту вновь созданную матрицу в конце.
- Если невозможно добраться до места назначения, напечатайте « Путь не существует» .
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <iostream> using namespace std; #define MAX 50 // Function to check whether the path exists bool hasPath( int maze[][MAX], int sol[][MAX], int N) { for ( int i = 0; i < N; i++) for ( int j = 0; j < N; j++) sol[i][j] = 0; // Declaring and initializing CRF // (can reach from) matrix bool ** CRF = new bool *[N]; for ( int i = 0; i < N; i++) CRF[i] = new bool [N]; for ( int i = 0; i < N; i++) for ( int j = 0; j < N; j++) CRF[i][j] = false ; CRF[N - 1][N - 1] = true ; // Using the DP to fill CRF matrix // in correct order for ( int k = N - 1; k >= 0; k--) { for ( int j = k; j >= 0; j--) { if (!(k == N - 1 && j == N - 1)) { // If it is possible to get // to a valid location from // cell maze[k][j] for ( int a = 0; a <= maze[k][j]; a++) { if ((j + a < N && CRF[k][j + a] == true ) || (k + a < N && CRF[k + a][j] == true )) { CRF[k][j] = true ; break ; } } // If it is possible to get to // a valid location from cell // maze[j][k] for ( int a = 0; a <= maze[j][k]; a++) { if ((k + a < N && CRF[j][k + a] == true ) || (j + a < N && CRF[j + a][k] == true )) { CRF[j][k] = true ; break ; } } } } } // If CRF[0][0] is false it means we cannot reach // the end of the maze at all if (CRF[0][0] == false ) return false ; // Filling the solution matrix using CRF int i = 0, j = 0; while (!(i == N - 1 && j == N - 1)) { sol[i][j] = 1; if (maze[i][j] > 0) // Get to a valid location from // the current cell for ( int a = 1; a <= maze[i][j]; a++) { if ((j + a < N && CRF[i][j + a] == true )) { j = j + a; break ; } else if ((i + a < N && CRF[i + a][j] == true )) { i = i + a; break ; } } } sol[N - 1][N - 1] = 1; return true ; } // Utility function to print the contents // of a 2-D array void printMatrix( int sol[][MAX], int N) { for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) cout << sol[i][j] << " " ; cout << "
" ; } } // Driver code int main() { int maze[][MAX] = { { 2, 2, 1, 1, 0 }, { 0, 0, 3, 0, 0 }, { 1, 0, 0, 0, 0 }, { 0, 0, 2, 0, 1 }, { 0, 0, 3, 0, 0 } }; int N = sizeof (maze) / sizeof (maze[0]); int sol[N][MAX]; // If path exists if (hasPath(maze, sol, N)) // Print the path printMatrix(sol, N); else cout << "No path exists" ; return 0; } |
Java
// Java implementation of the approach class GFG { static int MAX = 50 ; // Function to check whether the path exists static boolean hasPath( int maze[][], int sol[][], int N) { for ( int i = 0 ; i < N; i++) for ( int j = 0 ; j < N; j++) sol[i][j] = 0 ; // Declaring and initializing CRF // (can reach from) matrix boolean [][]CRF = new boolean [N][N]; CRF[N - 1 ][N - 1 ] = true ; // Using the DP to fill CRF matrix // in correct order for ( int k = N - 1 ; k >= 0 ; k--) { for ( int j = k; j >= 0 ; j--) { if (!(k == N - 1 && j == N - 1 )) { // If it is possible to get // to a valid location from // cell maze[k][j] for ( int a = 0 ; a <= maze[k][j]; a++) { if ((j + a < N && CRF[k][j + a] == true ) || (k + a < N && CRF[k + a][j] == true )) { CRF[k][j] = true ; break ; } } // If it is possible to get to // a valid location from cell // maze[j][k] for ( int a = 0 ; a <= maze[j][k]; a++) { if ((k + a < N && CRF[j][k + a] == true ) || (j + a < N && CRF[j + a][k] == true )) { CRF[j][k] = true ; break ; } } } } } // If CRF[0][0] is false it means we cannot reach // the end of the maze at all if (CRF[ 0 ][ 0 ] == false ) return false ; // Filling the solution matrix using CRF int i = 0 , j = 0 ; while (!(i == N - 1 && j == N - 1 )) { sol[i][j] = 1 ; if (maze[i][j] > 0 ) // Get to a valid location from // the current cell for ( int a = 1 ; a <= maze[i][j]; a++) { if ((j + a < N && CRF[i][j + a] == true )) { j = j + a; break ; } else if ((i + a < N && CRF[i + a][j] == true )) { i = i + a; break ; } } } sol[N - 1 ][N - 1 ] = 1 ; return true ; } // Utility function to print the contents // of a 2-D array static void printMatrix( int sol[][], int N) { for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < N; j++) System.out.print(sol[i][j] + " " ); System.out.println(); } } // Driver code public static void main(String[] args) { int maze[][] = {{ 2 , 2 , 1 , 1 , 0 }, { 0 , 0 , 3 , 0 , 0 }, { 1 , 0 , 0 , 0 , 0 }, { 0 , 0 , 2 , 0 , 1 }, { 0 , 0 , 3 , 0 , 0 }}; int N = maze.length; int [][]sol = new int [N][MAX]; // If path exists if (hasPath(maze, sol, N)) // Print the path printMatrix(sol, N); else System.out.println( "No path exists" ); } } // This code is contributed by Princi Singh |
C#
// C# implementation of the approach using System; class GFG { static int MAX = 50; // Function to check whether the path exists static Boolean hasPath( int [,]maze, int [,]sol, int N) { int i, j, k; for (i = 0; i < N; i++) for (j = 0; j < N; j++) sol[i, j] = 0; // Declaring and initializing CRF // (can reach from) matrix Boolean [,]CRF = new Boolean[N, N]; CRF[N - 1, N - 1] = true ; // Using the DP to fill CRF matrix // in correct order for (k = N - 1; k >= 0; k--) { for (j = k; j >= 0; j--) { if (!(k == N - 1 && j == N - 1)) { // If it is possible to get // to a valid location from // cell maze[k,j] for ( int a = 0; a <= maze[k, j]; a++) { if ((j + a < N && CRF[k, j + a] == true ) || (k + a < N && CRF[k + a, j] == true )) { CRF[k, j] = true ; break ; } } // If it is possible to get to // a valid location from cell // maze[j,k] for ( int a = 0; a <= maze[j, k]; a++) { if ((k + a < N && CRF[j, k + a] == true ) || (j + a < N && CRF[j + a, k] == true )) &
РЕКОМЕНДУЕМЫЕ СТАТЬИ |