Dado un laberinto binario N * N donde un 0 indica que la posición se puede visitar y un 1 indica que la posición no se puede visitar sin una clave, la tarea es encontrar si es posible visitar la celda inferior derecha desde la parte superior. -Celda izquierda con una sola llave en el camino. Si es posible, escriba «Sí» , de lo contrario, escriba «No» .
Ejemplo:
Entrada: laberinto[][] = {
{0, 0, 1},
{1, 0, 1},
{1, 1, 0}}
Salida: Sí
Enfoque: este problema se puede resolver usando la recursividad , para cada movimiento posible, si la celda actual es 0 , entonces, sin alterar el estado de la clave, verifique si es el destino, de lo contrario avance. Si la celda actual es 1 , entonces se debe usar la clave, ahora para los movimientos posteriores, la clave se establecerá en falso , es decir, nunca se volverá a usar en la misma ruta. Si alguna ruta llega al destino, imprima Sí ; de lo contrario, imprima No.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Recursive function to check whether there is
// a path from the top left cell to the
// bottom right cell of the maze
bool findPath(vector<vector<int> > maze, int xpos, int ypos,
bool key)
{
// Check whether the current cell is
// within the maze
if (xpos < 0 || xpos >= maze.size() || ypos < 0
|| ypos >= maze.size())
return false;
// If key is required to move further
if (maze[xpos][ypos] == '1') {
// If the key hasn't been used before
if (key == true)
// If current cell is the destination
if (xpos == maze.size() - 1
&& ypos == maze.size() - 1)
return true;
// Either go down or right
return findPath(maze, xpos + 1, ypos, false)
|| findPath(maze, xpos, ypos + 1, false);
// Key has been used before
return false;
}
// If current cell is the destination
if (xpos == maze.size() - 1 && ypos == maze.size() - 1)
return true;
// Either go down or right
return findPath(maze, xpos + 1, ypos, key)
|| findPath(maze, xpos, ypos + 1, key);
}
bool mazeProb(vector<vector<int> > maze, int xpos, int ypos)
{
bool key = true;
if (findPath(maze, xpos, ypos, key))
return true;
return false;
}
// Driver code
int main()
{
vector<vector<int> > maze = { { '0', '0', '1' },
{ '1', '0', '1' },
{ '1', '1', '0' } };
int n = maze.size();
// If there is a path from the cell (0, 0)
if (mazeProb(maze, 0, 0))
cout << "Yes";
else
cout << "No";
}
// This code is contributed by grand_master
Java
// Java implementation of the approach
import java.io.*;
import java.util.ArrayList;
class GFG {
// Recursive function to check whether there
// is a path from the top left cell to the
// bottom right cell of the maze
static boolean
findPath(ArrayList<ArrayList<Integer> > maze, int xpos,
int ypos, boolean key)
{
// Check whether the current cell is
// within the maze
if (xpos < 0 || xpos >= maze.size() || ypos < 0
|| ypos >= maze.size())
return false;
// If key is required to move further
if (maze.get(xpos).get(ypos) == '1') {
// If the key hasn't been used before
if (key == true)
// If current cell is the destination
if (xpos == maze.size() - 1
&& ypos == maze.size() - 1)
return true;
// Either go down or right
return findPath(maze, xpos + 1, ypos, false)
|| findPath(maze, xpos, ypos + 1, false);
}
// If current cell is the destination
if (xpos == maze.size() - 1
&& ypos == maze.size() - 1)
return true;
// Either go down or right
return findPath(maze, xpos + 1, ypos, key)
|| findPath(maze, xpos, ypos + 1, key);
}
static boolean
mazeProb(ArrayList<ArrayList<Integer> > maze, int xpos,
int ypos)
{
boolean key = true;
if (findPath(maze, xpos, ypos, key))
return true;
return false;
}
// Driver code
public static void main(String[] args)
{
int size = 3;
ArrayList<ArrayList<Integer> > maze
= new ArrayList<ArrayList<Integer> >(size);
for (int i = 0; i < size; i++) {
maze.add(new ArrayList<Integer>());
}
// We are making these
//{ { '0', '0', '1' },
// { '1', '0', '1' },
// { '1', '1', '0' } };
maze.get(0).add(0);
maze.get(0).add(0);
maze.get(0).add(1);
maze.get(1).add(1);
maze.get(1).add(0);
maze.get(1).add(1);
maze.get(2).add(1);
maze.get(2).add(1);
maze.get(2).add(0);
// If there is a path from the cell (0, 0)
if (mazeProb(maze, 0, 0))
System.out.print("Yes");
else
System.out.print("No");
}
}
// This code is contributed by sujitmeshram
Python3
# Python3 implementation of the approach
# Recursive function to check whether there is
# a path from the top left cell to the
# bottom right cell of the maze
def findPath(maze, xpos, ypos, key):
# Check whether the current cell is
# within the maze
if xpos < 0 or xpos >= len(maze) or ypos < 0 \
or ypos >= len(maze):
return False
# If key is required to move further
if maze[xpos][ypos] == '1':
# If the key hasn't been used before
if key == True:
# If current cell is the destination
if xpos == len(maze)-1 and ypos == len(maze)-1:
return True
# Either go down or right
return findPath(maze, xpos + 1, ypos, False) or \
findPath(maze, xpos, ypos + 1, False)
# Key has been used before
return False
# If current cell is the destination
if xpos == len(maze)-1 and ypos == len(maze)-1:
return True
# Either go down or right
return findPath(maze, xpos + 1, ypos, key) or \
findPath(maze, xpos, ypos + 1, key)
def mazeProb(maze, xpos, ypos):
key = True
if findPath(maze, xpos, ypos, key):
return True
return False
# Driver code
if __name__ == "__main__":
maze = [['0', '0', '1'],
['1', '0', '1'],
['1', '1', '0']]
n = len(maze)
# If there is a path from the cell (0, 0)
if mazeProb(maze, 0, 0):
print("Yes")
else:
print("No")
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG {
// Recursive function to check whether there
// is a path from the top left cell to the
// bottom right cell of the maze
static bool findPath(List<List<int> > maze, int xpos,
int ypos, bool key)
{
// Check whether the current cell is
// within the maze
if (xpos < 0 || xpos >= maze.Count || ypos < 0
|| ypos >= maze.Count)
return false;
// If key is required to move further
if (maze[xpos][ypos] == '1') {
// If the key hasn't been used before
if (key == true)
// If current cell is the destination
if (xpos == maze.Count - 1
&& ypos == maze.Count - 1)
return true;
// Either go down or right
return findPath(maze, xpos + 1, ypos, false)
|| findPath(maze, xpos, ypos + 1, false);
}
// If current cell is the destination
if (xpos == maze.Count - 1
&& ypos == maze.Count - 1)
return true;
// Either go down or right
return findPath(maze, xpos + 1, ypos, key)
|| findPath(maze, xpos, ypos + 1, key);
}
static bool mazeProb(List<List<int> > maze, int xpos,
int ypos)
{
bool key = true;
if (findPath(maze, xpos, ypos, key))
return true;
return false;
}
// Driver code
public static void Main(String[] args)
{
int size = 3;
List<List<int> > maze = new List<List<int> >(size);
for (int i = 0; i < size; i++) {
maze.Add(new List<int>());
}
// We are making these
//{ { '0', '0', '1' },
// { '1', '0', '1' },
// { '1', '1', '0' } };
maze[0].Add(0);
maze[0].Add(0);
maze[0].Add(1);
maze[1].Add(1);
maze[1].Add(0);
maze[1].Add(1);
maze[2].Add(1);
maze[2].Add(1);
maze[2].Add(0);
// If there is a path from the cell (0, 0)
if (mazeProb(maze, 0, 0))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// JavaScript implementation of the approach
// Recursive function to check whether there is
// a path from the top left cell to the
// bottom right cell of the maze
function findPath(maze, xpos, ypos, key)
{
// Check whether the current cell is
// within the maze
if (xpos < 0 || xpos >= maze.length ||
ypos < 0 || ypos >= maze.length)
return false;
// If key is required to move further
if (maze[xpos][ypos] == '1')
{
// If the key hasn't been used before
if (key == true)
// If current cell is the destination
if (xpos == maze.length - 1 &&
ypos == maze.length - 1)
return true;
// Either go down or right
return findPath(maze, xpos + 1,
ypos, false) ||
findPath(maze, xpos,
ypos + 1, false);
// Key has been used before
return false;
}
// If current cell is the destination
if (xpos == maze.length - 1 &&
ypos == maze.length - 1)
return true;
// Either go down or right
return findPath(maze, xpos + 1,
ypos, key) ||
findPath(maze, xpos,
ypos + 1, key);
}
function mazeProb(maze, xpos, ypos)
{
let key = true;
if (findPath(maze, xpos, ypos, key))
return true;
return false;
}
// Driver code
let maze = [ [ '0', '0', '1' ],
[ '1', '0', '1' ],
[ '1', '1', '0' ] ];
let n = maze.length;
// If there is a path from the cell (0, 0)
if (mazeProb(maze, 0, 0))
document.write("Yes");
else
document.write("No");
</script>
Producción
Yes
Complejidad del tiempo: O(2 N )
Enfoque optimizado:
La programación dinámica se puede utilizar para mejorar la complejidad del tiempo.
La idea principal es que para cada celda la respuesta depende de su fila y columna anterior.
Aquí maze[1][1] depende de maze[1][0] o maze[0][1] si es un camino posible.
Por lo tanto, al usar este enfoque, podemos calcular el resultado del laberinto [n-1] [n-1] a partir de sus celdas adyacentes anteriores
Y también hay algunas condiciones de borde para la fila 0 y la columna 0, ya que estas celdas dependen de su columna y fila anteriores, respectivamente.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
bool mazeProb(vector<vector<int> > maze, int n)
{
for (int row = 0; row < n; ++row) {
for (int col = 0; col < n; ++col) {
if (row == 0 && col == 0) // Skip the first cell
continue;
if (row == 0) {
// for first row result depend on previous col
maze[row][col] = min(
2, maze[row][col] + maze[row][col - 1]);
}
else if (col == 0) {
// for first col result depends on previous row
maze[row][col] = min(
2, maze[row][col] + maze[row - 1][col]);
}
else {
// for other cells, result will be
// minimum of previous row or col cell
maze[row][col]
= min(2, maze[row][col]
+ min(maze[row][col - 1],
maze[row - 1][col]));
}
}
}
return maze[n - 1][n - 1]
!= 2; // if last cell value is 2 then there is no
// path available
}
// Driver code
int main()
{
vector<vector<int> > maze
= { { 0, 0, 1 }, { 1, 0, 1 }, { 1, 1, 0 } };
int n = maze.size();
// If there is a path from the cell (0, 0)
if (mazeProb(maze, 3))
cout << "Yes";
else
cout << "No";
}
// This code is contributed by pratham sonawane
Java
// Java implementation of the approach
import java.util.ArrayList;
public class GFG {
static boolean mazeProb(ArrayList<int[]> maze, int n)
{
for (int row = 0; row < n; ++row) {
for (int col = 0; col < n; ++col) {
if (row == 0
&& col == 0) // Skip the first cell
continue;
if (row == 0) {
// for first row result depend on
// previous col
maze.get(row)[col] = Math.min(
2, maze.get(row)[col]
+ maze.get(row)[col - 1]);
}
else if (col == 0) {
// for first col result depends on
// previous row
maze.get(row)[col] = Math.min(
2, maze.get(row)[col]
+ maze.get(row - 1)[col]);
}
else {
// for other cells, result will be
// minimum of previous row or col cell
maze.get(row)[col] = Math.min(
2, maze.get(row)[col]
+ Math.min(
maze.get(row)[col - 1],
maze.get(row - 1)[col]));
}
}
}
return maze.get(n - 1)[n - 1]
!= 2; // if last cell value is 2 then there is
// no path available
}
// Driver code
public static void main(String[] args)
{
ArrayList<int[]> maze = new ArrayList<int[]>();
maze.add(new int[] { 0, 0, 1 });
maze.add(new int[] { 1, 0, 1 });
maze.add(new int[] { 1, 1, 0 });
int n = maze.size();
// If there is a path from the cell (0, 0)
if (mazeProb(maze, 3))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Lovely Jain
Python3
# Python implementation of the approach
def mazeProb(maze, n):
for row in range(n):
for col in range(n):
if (row == 0 and col == 0): # Skip the first cell
continue
if (row == 0):
# for first row result depend on previous col
maze[row][col] = min(
2, maze[row][col] + maze[row][col - 1])
elif (col == 0):
# for first col result depends on previous row
maze[row][col] = min(
2, maze[row][col] + maze[row - 1][col])
else:
# for other cells, result will be
# minimum of previous row or col cell
maze[row][col] = min(2, maze[row][col] + min(maze[row][col - 1], maze[row - 1][col]))
return maze[n - 1][n - 1]!= 2 # if last cell value is 2 then there is no
# path available
# Driver code
maze = [ [ 0, 0, 1 ], [ 1, 0, 1 ], [ 1, 1, 0 ] ]
n = len(maze)
# If there is a path from the cell (0, 0)
if (mazeProb(maze, 3)):
print("Yes")
else:
print("No")
# This code is contributed by shinjanpatra
Javascript
<script>
// JavaScript implementation of the approach
function mazeProb(maze,n)
{
for (let row = 0; row < n; ++row) {
for (let col = 0; col < n; ++col) {
if (row == 0 && col == 0) // Skip the first cell
continue;
if (row == 0) {
// for first row result depend on previous col
maze[row][col] = Math.min(
2, maze[row][col] + maze[row][col - 1]);
}
else if (col == 0) {
// for first col result depends on previous row
maze[row][col] = Math.min(
2, maze[row][col] + maze[row - 1][col]);
}
else {
// for other cells, result will be
// minimum of previous row or col cell
maze[row][col]
= Math.min(2, maze[row][col]
+ Math.min(maze[row][col - 1],
maze[row - 1][col]));
}
}
}
return maze[n - 1][n - 1]!= 2; // if last cell value is 2 then there is no
// path available
}
// Driver code
let maze = [ [ 0, 0, 1 ], [ 1, 0, 1 ], [ 1, 1, 0 ] ];
let n = maze.length;
// If there is a path from the cell (0, 0)
if (mazeProb(maze, 3))
document.write("Yes");
else
document.write("No");
// This code is contributed by shinjanpatra
</script>
Producción
Yes
Complejidad del tiempo: O(N^2)
Complejidad espacial: O(1)