Dada una array grid[][] de dimensiones M * N , tres enteros X, Y y K , la tarea es verificar si existe algún camino desde la celda (X, Y) a cualquier celda límite de la array tal que la suma de los elementos de la array presentes en el camino es como máximo K . Si no existe tal ruta, escriba «No» . De lo contrario, escriba «Sí» . Los movimientos posibles desde cualquier celda son arriba , abajo , izquierda o derecha .
Ejemplos:
Entrada: rejilla[][] = {{25, 5, 25, 25, 25, 25}, {25, 1, 1, 5, 12, 25}, {25, 1, 12, 0, 15, 25} , {22, 1, 11, 2, 19, 15}, {25, 2, 2, 1, 12, 15}, {25, 9, 10, 1, 11, 25}, {25, 25, 25, 25, 25, 25}}, X = 2, Y = 3, K = 17
Salida: Sí
Explicación:
La siguiente imagen ilustra una de las formas posibles de llegar a un elemento límite de la array dada desde la celda (2, 3):
La ruta en cuestión es (2, 3) -> (3, 3) -> (4, 3) -> (4, 2) -> (4, 1) -> (3, 1) -> (2, 1) ) -> (1, 1).
El costo del camino = 0 + 2 + 1 + 2 + 2 + 1 + 1 + 1 + 0 = 15( < K).Entrada: grid[][] = {{1, 2, 3}, {1, 2, 3}, {3, 4, 5}}, X = 1, Y = 1, K = 0
Salida: -1
Enfoque: el problema dado se puede resolver utilizando Backtracking para considerar todos los caminos posibles desde la celda inicial dada, y verificar si existe algún camino hasta una celda límite de la array dada que tenga la suma de sus elementos constituyentes igual a K o no .
Siga los pasos a continuación para resolver el problema:
- Defina una función recursiva , digamos findPath(X, Y, K, board) , para verificar si existe alguna ruta desde la celda inicial (X, Y) a cualquier elemento de límite o no.
- Caso base: si se alcanza X < 0 o Y < 0 o X >= M o Y >= N , entonces devuelve true .
- Ahora, verifique si grid[X][Y] >= K o no. Si se determina que es cierto, marque la celda actual visitada. Disminuya K por el valor de grid[X][Y] y luego visite las celdas adyacentes no visitadas, es decir, llame recursivamente a findPath(X + 1, Y, K), findPath(X, Y + 1, K), findPath(X – 1, Y, K) y findPath(X, Y – 1, K) .
- Si alguna de las llamadas recursivas anteriores devuelve true , devuelve true desde la llamada recursiva actual.
- De lo contrario, marque la celda actual como no visitada.
- Si ninguna de las condiciones anteriores satisface, devuelva false de la llamada recursiva actual.
- Ahora, si la función findPath(X, Y, K) devuelve verdadero, entonces imprime «Sí» . De lo contrario, escriba “No” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if it is valid
// to move to the given index or not
bool isValid(vector<vector<int> >& board,
int i, int j, int K)
{
if (board[i][j] <= K) {
return true;
}
// Otherwise return false
return false;
}
// Function to check if there exists a
// path from the cell (X, Y) of the
// matrix to any boundary cell with
// sum of elements at most K or not
bool findPath(vector<vector<int> >& board,
int X, int Y,
int M, int N, int K)
{
// Base Case
if (X < 0 || X == M
|| Y < 0 || Y == N) {
return true;
}
// If K >= board[X][Y]
if (isValid(board, X, Y, K)) {
// Stores the current element
int board_XY = board[X][Y];
// Mark the current cell as visited
board[X][Y] = INT_MAX;
// Visit all the adjacent cells
if (findPath(board, X + 1, Y, M,
N, K - board_XY)
|| findPath(board, X - 1, Y, M,
N, K - board_XY)
|| findPath(board, X, Y + 1, M,
N, K - board_XY)
|| findPath(board, X, Y - 1, M,
N, K - board_XY)) {
return true;
}
// Mark the cell unvisited
board[X][Y] = board_XY;
}
// Return false
return false;
}
// Driver Code
int main()
{
vector<vector<int> > grid = {
{ 25, 5, 25, 25, 25, 25 },
{ 25, 1, 1, 5, 12, 25 },
{ 25, 1, 12, 0, 15, 25 },
{ 22, 1, 11, 2, 19, 15 },
{ 25, 2, 2, 1, 12, 15 },
{ 25, 9, 10, 1, 11, 25 },
{ 25, 25, 25, 25, 25, 25 }
};
int K = 17;
int M = grid.size();
int N = grid[0].size();
int X = 2, Y = 3;
if (findPath(grid, X, Y, M, N, K))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to check if it is valid
// to move to the given index or not
static boolean isValid(int[][] board, int i,
int j, int K)
{
if (board[i][j] <= K)
{
return true;
}
// Otherwise return false
return false;
}
// Function to check if there exists a
// path from the cell (X, Y) of the
// matrix to any boundary cell with
// sum of elements at most K or not
static boolean findPath(int[][] board, int X, int Y,
int M, int N, int K)
{
// Base Case
if (X < 0 || X == M || Y < 0 || Y == N)
{
return true;
}
// If K >= board[X][Y]
if (isValid(board, X, Y, K))
{
// Stores the current element
int board_XY = board[X][Y];
// Mark the current cell as visited
board[X][Y] = Integer.MAX_VALUE;
// Visit all the adjacent cells
if (findPath(board, X + 1, Y, M, N,
K - board_XY) ||
findPath(board, X - 1, Y, M, N,
K - board_XY) ||
findPath(board, X, Y + 1, M, N,
K - board_XY) ||
findPath(board, X, Y - 1, M, N,
K - board_XY))
{
return true;
}
// Mark the cell unvisited
board[X][Y] = board_XY;
}
// Return false
return false;
}
// Driver Code
public static void main(String[] args)
{
int[][] grid = { { 25, 5, 25, 25, 25, 25 },
{ 25, 1, 1, 5, 12, 25 },
{ 25, 1, 12, 0, 15, 25 },
{ 22, 1, 11, 2, 19, 15 },
{ 25, 2, 2, 1, 12, 15 },
{ 25, 9, 10, 1, 11, 25 },
{ 25, 25, 25, 25, 25, 25 } };
int K = 17;
int M = grid.length;
int N = grid[0].length;
int X = 2, Y = 3;
if (findPath(grid, X, Y, M, N, K))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by ukasp
Python3
# Python3 program for the above approach
import sys
INT_MAX = sys.maxsize
# Function to check if it is valid
# to move to the given index or not
def isValid(board, i, j, K):
if (board[i][j] <= K):
return True
# Otherwise return false
return False
# Function to check if there exists a
# path from the cell (X, Y) of the
# matrix to any boundary cell with
# sum of elements at most K or not
def findPath(board, X, Y, M, N, K):
# Base Case
if (X < 0 or X == M or
Y < 0 or Y == N):
return True
# If K >= board[X][Y]
if (isValid(board, X, Y, K)):
# Stores the current element
board_XY = board[X][Y]
# Mark the current cell as visited
board[X][Y] = INT_MAX
# Visit all the adjacent cells
if (findPath(board, X + 1, Y, M,
N, K - board_XY) or
findPath(board, X - 1, Y, M,
N, K - board_XY) or
findPath(board, X, Y + 1, M,
N, K - board_XY) or
findPath(board, X, Y - 1, M,
N, K - board_XY)):
return True;
# Mark the cell unvisited
board[X][Y] = board_XY
# Return false
return False
# Driver Code
if __name__ == "__main__":
grid = [
[ 25, 5, 25, 25, 25, 25 ],
[ 25, 1, 1, 5, 12, 25 ],
[ 25, 1, 12, 0, 15, 25 ],
[ 22, 1, 11, 2, 19, 15 ],
[ 25, 2, 2, 1, 12, 15 ],
[ 25, 9, 10, 1, 11, 25 ],
[ 25, 25, 25, 25, 25, 25 ] ]
K = 17
M = len(grid)
N = len(grid[0])
X = 2
Y = 3
if (findPath(grid, X, Y, M, N, K)):
print("Yes")
else:
print("No")
# This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if it is valid
// to move to the given index or not
static bool isValid(int[,] board, int i,
int j, int K)
{
if (board[i, j] <= K)
{
return true;
}
// Otherwise return false
return false;
}
// Function to check if there exists a
// path from the cell (X, Y) of the
// matrix to any boundary cell with
// sum of elements at most K or not
static bool findPath(int[,] board, int X, int Y,
int M, int N, int K)
{
// Base Case
if (X < 0 || X == M ||
Y < 0 || Y == N)
{
return true;
}
// If K >= board[X][Y]
if (isValid(board, X, Y, K))
{
// Stores the current element
int board_XY = board[X, Y];
// Mark the current cell as visited
board[X, Y] = int.MaxValue;
// Visit all the adjacent cells
if (findPath(board, X + 1, Y, M, N,
K - board_XY) ||
findPath(board, X - 1, Y, M, N,
K - board_XY) ||
findPath(board, X, Y + 1, M, N,
K - board_XY) ||
findPath(board, X, Y - 1, M, N,
K - board_XY))
{
return true;
}
// Mark the cell unvisited
board[X, Y] = board_XY;
}
// Return false
return false;
}
// Driver Code
public static void Main(string[] args)
{
int[,] grid = { { 25, 5, 25, 25, 25, 25 },
{ 25, 1, 1, 5, 12, 25 },
{ 25, 1, 12, 0, 15, 25 },
{ 22, 1, 11, 2, 19, 15 },
{ 25, 2, 2, 1, 12, 15 },
{ 25, 9, 10, 1, 11, 25 },
{ 25, 25, 25, 25, 25, 25 } };
int K = 17;
int M = grid.Length;
int N = grid.GetLength(0);
int X = 2, Y = 3;
if (findPath(grid, X, Y, M, N, K))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by AnkThon
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to check if it is valid
// to move to the given index or not
function isValid(board, i, j, K)
{
if (board[i][j] <= K)
{
return true;
}
// Otherwise return false
return false;
}
// Function to check if there exists a
// path from the cell (X, Y) of the
// matrix to any boundary cell with
// sum of elements at most K or not
function findPath(board, X, Y,
M, N, K)
{
// Base Case
if (X < 0 || X == M || Y < 0 || Y == N)
{
return true;
}
// If K >= board[X][Y]
if (isValid(board, X, Y, K))
{
// Stores the current element
let board_XY = board[X][Y];
// Mark the current cell as visited
board[X][Y] = Number.MAX_VALUE;
// Visit all the adjacent cells
if (findPath(board, X + 1, Y, M, N,
K - board_XY) ||
findPath(board, X - 1, Y, M, N,
K - board_XY) ||
findPath(board, X, Y + 1, M, N,
K - board_XY) ||
findPath(board, X, Y - 1, M, N,
K - board_XY))
{
return true;
}
// Mark the cell unvisited
board[X][Y] = board_XY;
}
// Return false
return false;
}
// Driver code
let grid = [[ 25, 5, 25, 25, 25, 25 ],
[ 25, 1, 1, 5, 12, 25 ],
[ 25, 1, 12, 0, 15, 25 ],
[ 22, 1, 11, 2, 19, 15 ],
[ 25, 2, 2, 1, 12, 15 ],
[ 25, 9, 10, 1, 11, 25 ],
[ 25, 25, 25, 25, 25, 25 ]];
let K = 17;
let M = grid.length;
let N = grid[0].length;
let X = 2, Y = 3;
if (findPath(grid, X, Y, M, N, K))
document.write("Yes");
else
document.write("No");
// This code is contributed by susmitakundugoaldanga.
</script>
Producción:
Yes
Complejidad de Tiempo: O(3 N * M )
Espacio Auxiliar: O(N * M)