Dado un laberinto cuadrado que contiene números positivos, encuentre todos los caminos desde una celda de la esquina (cualquiera de las cuatro esquinas extremas) hasta la celda del medio. Podemos movernos exactamente n pasos desde una celda en 4 direcciones, es decir, norte, este, oeste y sur, donde n es el valor de la celda ,
Podemos pasar a mat[i+n][j], mat[in][j], mat[i][j+n] y mat[i][jn] desde una celda mat[i][j] donde n es el valor de mat[i][j].
Ejemplo
Input: 9 x 9 maze [ 3, 5, 4, 4, 7, 3, 4, 6, 3 ] [ 6, 7, 5, 6, 6, 2, 6, 6, 2 ] [ 3, 3, 4, 3, 2, 5, 4, 7, 2 ] [ 6, 5, 5, 1, 2, 3, 6, 5, 6 ] [ 3, 3, 4, 3, 0, 1, 4, 3, 4 ] [ 3, 5, 4, 3, 2, 2, 3, 3, 5 ] [ 3, 5, 4, 3, 2, 6, 4, 4, 3 ] [ 3, 5, 1, 3, 7, 5, 3, 6, 4 ] [ 6, 2, 4, 3, 4, 5, 4, 5, 1 ] Output: (0, 0) -> (0, 3) -> (0, 7) -> (6, 7) -> (6, 3) -> (3, 3) -> (3, 4) -> (5, 4) -> (5, 2) -> (1, 2) -> (1, 7) -> (7, 7) -> (7, 1) -> (2, 1) -> (2, 4) -> (4, 4) -> MID
La idea es utilizar el retroceso. Comenzamos con cada celda de la esquina del laberinto y verificamos recursivamente si conduce a la solución o no. El siguiente es el algoritmo de retroceso:
si se alcanza el destino
- imprime la ruta
Más
- Marque la celda actual como visitada y agréguela a la array de ruta.
- Avanza en las 4 direcciones permitidas y verifica recursivamente si alguna de ellas conduce a una solución.
- Si ninguna de las soluciones anteriores funciona, marque esta celda como no visitada y elimínela de la array de rutas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find a path from corner cell to
// middle cell in maze containing positive numbers
#include <bits/stdc++.h>
using namespace std;
// Rows and columns in given maze
#define N 9
// check whether given cell is a valid cell or not.
bool isValid(set<pair<int, int> > visited,
pair<int, int> pt)
{
// check if cell is not visited yet to
// avoid cycles (infinite loop) and its
// row and column number is in range
return (pt.first >= 0) && (pt.first < N) &&
(pt.second >= 0) && (pt.second < N) &&
(visited.find(pt) == visited.end());
}
// Function to print path from source to middle coordinate
void printPath(list<pair<int, int> > path)
{
for (auto it = path.begin(); it != path.end(); it++)
cout << "(" << it->first << ", "
<< it->second << ") -> ";
cout << "MID" << endl << endl;
}
// For searching in all 4 direction
int row[] = {-1, 1, 0, 0};
int col[] = { 0, 0, -1, 1};
// Coordinates of 4 corners of matrix
int _row[] = { 0, 0, N-1, N-1};
int _col[] = { 0, N-1, 0, N-1};
void findPathInMazeUtil(int maze[N][N],
list<pair<int, int> > &path,
set<pair<int, int> > &visited,
pair<int, int> &curr)
{
// If we have reached the destination cell.
// print the complete path
if (curr.first == N / 2 && curr.second == N / 2)
{
printPath(path);
return;
}
// consider each direction
for (int i = 0; i < 4; ++i)
{
// get value of current cell
int n = maze[curr.first][curr.second];
// We can move N cells in either of 4 directions
int x = curr.first + row[i]*n;
int y = curr.second + col[i]*n;
// Constructs a pair object with its first element
// set to x and its second element set to y
pair<int, int> next = make_pair(x, y);
// if valid pair
if (isValid(visited, next))
{
// mark cell as visited
visited.insert(next);
// add cell to current path
path.push_back(next);
// recurse for next cell
findPathInMazeUtil(maze, path, visited, next);
// backtrack
path.pop_back();
// remove cell from current path
visited.erase(next);
}
}
}
// Function to find a path from corner cell to
// middle cell in maze containing positive numbers
void findPathInMaze(int maze[N][N])
{
// list to store complete path
// from source to destination
list<pair<int, int> > path;
// to store cells already visited in current path
set<pair<int, int> > visited;
// Consider each corners as the starting
// point and search in maze
for (int i = 0; i < 4; ++i)
{
int x = _row[i];
int y = _col[i];
// Constructs a pair object
pair<int, int> pt = make_pair(x, y);
// mark cell as visited
visited.insert(pt);
// add cell to current path
path.push_back(pt);
findPathInMazeUtil(maze, path, visited, pt);
// backtrack
path.pop_back();
// remove cell from current path
visited.erase(pt);
}
}
int main()
{
int maze[N][N] =
{
{ 3, 5, 4, 4, 7, 3, 4, 6, 3 },
{ 6, 7, 5, 6, 6, 2, 6, 6, 2 },
{ 3, 3, 4, 3, 2, 5, 4, 7, 2 },
{ 6, 5, 5, 1, 2, 3, 6, 5, 6 },
{ 3, 3, 4, 3, 0, 1, 4, 3, 4 },
{ 3, 5, 4, 3, 2, 2, 3, 3, 5 },
{ 3, 5, 4, 3, 2, 6, 4, 4, 3 },
{ 3, 5, 1, 3, 7, 5, 3, 6, 4 },
{ 6, 2, 4, 3, 4, 5, 4, 5, 1 }
};
findPathInMaze(maze);
return 0;
}
Producción :
(0, 0) -> (0, 3) -> (0, 7) -> (6, 7) -> (6, 3) -> (3, 3) -> (3, 4) -> (5, 4) -> (5, 2) -> (1, 2) -> (1, 7) -> (7, 7) -> (7, 1) -> (2, 1) -> (2, 4) -> (4, 4) -> MID
Un mejor enfoque:
C++
// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
void printPath(vector<vector<int>>&maze, int i, int j, string ans){
// If we reach the center cell
if (i == maze.size()/2 && j==maze.size()/2){
// Make the final answer, Print the
// final answer and Return
ans += "(";
ans += to_string(i);
ans += ", ";
ans += to_string(j);
ans += ") -> MID";
cout<<ans<<endl;
return;
}
// If the element at the current position
// in maze is 0, simply Return as it has
// been visited before.
if (maze[i][j]==0){
return;
}
// If element is non-zero, then note
// the element in variable 'k'
int k = maze[i][j];
// Mark the cell visited by making the
// element 0. Don't worry, the element
// is safe in 'k'
maze[i][j]=0;
// Make recursive calls in all 4
// directions pro-actively i.e. if the next
// cell lies in maze or not. Right call
ans += "(";
ans += to_string(i);
ans += ", ";
ans += to_string(j);
ans += ") -> ";
if (j+k<maze.size()){
printPath(maze, i, j+k, ans);
}
// down call
if (i+k<maze.size()){
printPath(maze, i+k, j,ans);
}
// left call
if (j-k>0){
printPath(maze, i, j-k, ans);
}
// up call
if (i-k>0){
printPath(maze, i-k, j, ans);
}
// Unmark the visited cell by substituting
// its original value from 'k'
maze[i][j] = k;
}
int main () {
// Creating the maze
vector<vector<int>>maze = {
{ 3, 5, 4, 4, 7, 3, 4, 6, 3 },
{ 6, 7, 5, 6, 6, 2, 6, 6, 2 },
{ 3, 3, 4, 3, 2, 5, 4, 7, 2 },
{ 6, 5, 5, 1, 2, 3, 6, 5, 6 },
{ 3, 3, 4, 3, 0, 1, 4, 3, 4 },
{ 3, 5, 4, 3, 2, 2, 3, 3, 5 },
{ 3, 5, 4, 3, 2, 6, 4, 4, 3 },
{ 3, 5, 1, 3, 7, 5, 3, 6, 4 },
{ 6, 2, 4, 3, 4, 5, 4, 5, 1 }
};
// Calling the printPath function
printPath(maze,0,0,"");
}
// This code is contributed by shinjanpatra
Java
// Java program to find a path from corner cell to
// middle cell in maze containing positive numbers
import java.io.*;
class GFG {
public static void main (String[] args) {
// Creating the maze
int[][] maze = {
{ 3, 5, 4, 4, 7, 3, 4, 6, 3 },
{ 6, 7, 5, 6, 6, 2, 6, 6, 2 },
{ 3, 3, 4, 3, 2, 5, 4, 7, 2 },
{ 6, 5, 5, 1, 2, 3, 6, 5, 6 },
{ 3, 3, 4, 3, 0, 1, 4, 3, 4 },
{ 3, 5, 4, 3, 2, 2, 3, 3, 5 },
{ 3, 5, 4, 3, 2, 6, 4, 4, 3 },
{ 3, 5, 1, 3, 7, 5, 3, 6, 4 },
{ 6, 2, 4, 3, 4, 5, 4, 5, 1 }
};
// Calling the printPath function
printPath(maze,0,0,"");
}
public static void printPath(int[][] maze, int i, int j, String ans){
// If we reach the center cell
if (i == maze.length/2 && j==maze.length/2){
// Make the final answer, Print the
// final answer and Return
ans += "("+i+", "+j+") -> MID";
System.out.println(ans);
return;
}
// If the element at the current position
// in maze is 0, simply Return as it has
// been visited before.
if (maze[i][j]==0){
return;
}
// If element is non-zero, then note
// the element in variable 'k'
int k = maze[i][j];
// Mark the cell visited by making the
// element 0. Don't worry, the element
// is safe in 'k'
maze[i][j]=0;
// Make recursive calls in all 4
// directions pro-actively i.e. if the next
// cell lies in maze or not. Right call
if (j+k<maze.length){
printPath(maze, i, j+k, ans+"("+i+", "+j+") -> ");
}
// down call
if (i+k<maze.length){
printPath(maze, i+k, j, ans+"("+i+", "+j+") -> ");
}
// left call
if (j-k>0){
printPath(maze, i, j-k, ans+"("+i+", "+j+") -> ");
}
// up call
if (i-k>0){
printPath(maze, i-k, j, ans+"("+i+", "+j+") -> ");
}
// Unmark the visited cell by substituting
// its original value from 'k'
maze[i][j] = k;
}
}
Python3
# Python program to find a path from corner cell to
# middle cell in maze containing positive numbers
def printPath(maze, i, j, ans):
# If we reach the center cell
if (i == len(maze) // 2 and j == len(maze) // 2):
# Make the final answer, Print
# final answer and Return
ans += "(" + str(i) + ", " + str(j) + ") -> MID";
print(ans);
return;
# If the element at the current position
# in maze is 0, simply Return as it has
# been visited before.
if (maze[i][j] == 0):
return;
# If element is non-zero, then note
# the element in variable 'k'
k = maze[i][j];
# Mark the cell visited by making the
# element 0. Don't worry, the element
# is safe in 'k'
maze[i][j] = 0;
# Make recursive calls in all 4
# directions pro-actively i.e. if the next
# cell lies in maze or not. Right call
if (j + k < len(maze)):
printPath(maze, i, j + k, ans + "(" + str(i) + ", " + str(j) + ") -> ");
# down call
if (i + k < len(maze)):
printPath(maze, i + k, j, ans + "(" + str(i) + ", " + str(j) + ") -> ");
# left call
if (j - k > 0):
printPath(maze, i, j - k, ans + "(" + str(i) + ", " + str(j) + ") -> ");
# up call
if (i - k > 0):
printPath(maze, i - k, j, ans + "(" + str(i) + ", " + str(j) + ") -> ");
# Unmark the visited cell by substituting
# its original value from 'k'
maze[i][j] = k;
# Driver code
if __name__ == '__main__':
# Creating the maze
maze = [[ 3, 5, 4, 4, 7, 3, 4, 6, 3 ],[ 6, 7, 5, 6, 6, 2, 6, 6, 2 ],[ 3, 3, 4, 3, 2, 5, 4, 7, 2 ],
[ 6, 5, 5, 1, 2, 3, 6, 5, 6 ],[ 3, 3, 4, 3, 0, 1, 4, 3, 4 ],[ 3, 5, 4, 3, 2, 2, 3, 3, 5 ],
[ 3, 5, 4, 3, 2, 6, 4, 4, 3 ],[ 3, 5, 1, 3, 7, 5, 3, 6, 4 ],[ 6, 2, 4, 3, 4, 5, 4, 5, 1 ]] ;
# Calling the printPath function
printPath(maze, 0, 0, "");
# This code contributed by gauravrajput1
C#
// C# program to find a path from corner
// cell to middle cell in maze containing
// positive numbers
using System;
class GFG{
// Driver Code
public static void Main(String[] args)
{
// Creating the maze
int[,] maze = {
{ 3, 5, 4, 4, 7, 3, 4, 6, 3 },
{ 6, 7, 5, 6, 6, 2, 6, 6, 2 },
{ 3, 3, 4, 3, 2, 5, 4, 7, 2 },
{ 6, 5, 5, 1, 2, 3, 6, 5, 6 },
{ 3, 3, 4, 3, 0, 1, 4, 3, 4 },
{ 3, 5, 4, 3, 2, 2, 3, 3, 5 },
{ 3, 5, 4, 3, 2, 6, 4, 4, 3 },
{ 3, 5, 1, 3, 7, 5, 3, 6, 4 },
{ 6, 2, 4, 3, 4, 5, 4, 5, 1 }
};
// Calling the printPath function
printPath(maze, 0, 0, "");
}
public static void printPath(int[,] maze, int i,
int j, String ans)
{
// If we reach the center cell
if (i == maze.GetLength(0) / 2 &&
j == maze.GetLength(1) / 2)
{
// Make the readonly answer, Print the
// readonly answer and Return
ans += "(" + i + ", " + j + ") -> MID";
Console.WriteLine(ans);
return;
}
// If the element at the current position
// in maze is 0, simply Return as it has
// been visited before.
if (maze[i, j] == 0)
{
return;
}
// If element is non-zero, then note
// the element in variable 'k'
int k = maze[i, j];
// Mark the cell visited by making the
// element 0. Don't worry, the element
// is safe in 'k'
maze[i, j] = 0;
// Make recursive calls in all 4
// directions pro-actively i.e. if the next
// cell lies in maze or not. Right call
if (j + k < maze.GetLength(1))
{
printPath(maze, i, j + k,
ans + "(" + i +
", " + j + ") -> ");
}
// Down call
if (i + k < maze.GetLength(0))
{
printPath(maze, i + k, j,
ans + "(" + i +
", " + j + ") -> ");
}
// Left call
if (j - k > 0)
{
printPath(maze, i, j - k,
ans + "(" + i +
", " + j + ") -> ");
}
// Up call
if (i - k > 0)
{
printPath(maze, i - k, j,
ans + "(" + i +
", " + j + ") -> ");
}
// Unmark the visited cell by substituting
// its original value from 'k'
maze[i, j] = k;
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program to find a path from corner cell to
// middle cell in maze containing positive numbers
function printPath( maze,i,j,ans)
{
// If we reach the center cell
if (i == Math.floor(maze.length/2) && j == Math.floor(maze.length/2))
{
// Make the final answer, Print the
// final answer and Return
ans += "("+i+", "+j+") -> MID";
document.write(ans+"<br>");
return;
}
// If the element at the current position
// in maze is 0, simply Return as it has
// been visited before.
if (maze[i][j] == 0){
return;
}
// If element is non-zero, then note
// the element in variable 'k'
let k = maze[i][j];
// Mark the cell visited by making the
// element 0. Don't worry, the element
// is safe in 'k'
maze[i][j] = 0;
// Make recursive calls in all 4
// directions pro-actively i.e. if the next
// cell lies in maze or not. Right call
if (j + k < maze.length){
printPath(maze, i, j+k, ans+"("+i+", "+j+") -> ");
}
// down call
if (i + k < maze.length){
printPath(maze, i+k, j, ans+"("+i+", "+j+") -> ");
}
// left call
if (j-k>0){
printPath(maze, i, j-k, ans+"("+i+", "+j+") -> ");
}
// up call
if (i-k>0){
printPath(maze, i-k, j, ans+"("+i+", "+j+") -> ");
}
// Unmark the visited cell by substituting
// its original value from 'k'
maze[i][j] = k;
}
let maze = [[ 3, 5, 4, 4, 7, 3, 4, 6, 3 ],[ 6, 7, 5, 6, 6, 2, 6, 6, 2 ],[ 3, 3, 4, 3, 2, 5, 4, 7, 2 ],
[ 6, 5, 5, 1, 2, 3, 6, 5, 6 ],[ 3, 3, 4, 3, 0, 1, 4, 3, 4 ],[ 3, 5, 4, 3, 2, 2, 3, 3, 5 ],
[ 3, 5, 4, 3, 2, 6, 4, 4, 3 ],[ 3, 5, 1, 3, 7, 5, 3, 6, 4 ],[ 6, 2, 4, 3, 4, 5, 4, 5, 1 ]] ;
printPath(maze, 0, 0, "");
// This code is contributed by unknown2108
</script>
Salida :
(0, 0) -> (0, 3) -> (0, 7) -> (6, 7) -> (6, 3) -> (3, 3) -> (3, 4) -> (5, 4) -> (5, 2) -> (1, 2) -> (1, 7) -> (7, 7) -> (7, 1) -> (2, 1) -> (2, 4) -> (4, 4) -> MID
Este artículo es una contribución de Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA