Dada una array mat[][] y un entero K, la tarea es encontrar la longitud del camino más corto en una array desde la esquina superior izquierda hasta la esquina inferior derecha tal que la diferencia entre los Nodes vecinos no exceda K.
Ejemplo:
Entrada: mat = {{-1, 0, 4, 3}, K = 4, src = {0, 0}, dest = {2, 3}
{ 6, 5, 7, 8},
{ 2, 1, 2, 0}}
Salida: 7
Explicación: La única ruta más corta donde la diferencia entre los Nodes vecinos no excede K es: -1 -> 0 ->4 -> 7 ->5 ->1 ->2 ->0Entrada: mat = {{-1, 0, 4, 3}, K = 5, src = {0, 0}, dest = {2, 3}
{ 6, 5, 7, 8},
{ 2, 1, 2, 0}}
Salida: 5
Enfoque: El problema dado se puede resolver usando la búsqueda primero en amplitud . La idea es dejar de explorar la ruta si la diferencia entre los Nodes vecinos excede K. Los siguientes pasos se pueden usar para resolver el problema:
- Aplique la búsqueda primero en amplitud en el Node de origen y visite los Nodes vecinos cuya diferencia absoluta entre sus valores y el valor del Node actual no sea mayor que K
- Se utiliza una array booleana para realizar un seguimiento de las celdas visitadas de la array.
- Después de llegar al Node de destino devuelve la distancia recorrida.
- Si no se puede alcanzar el Node de destino, devuelva -1
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int dist, i, j, val;
// Constructor
Node(int x, int y, int d, int v)
{
i = x;
j = y;
dist = d;
val = v;
}
};
// Function to find the length of the
// shortest path with neighbor nodes
// value not exceeding K
int shortestPathLessThanK(vector<vector<int> > mat, int K,
int src[], int dest[])
{
// Initialize a queue
queue<Node*> q;
// Add the source node
// into the queue
Node* Nw
= new Node(src[0], src[1], 0, mat[src[0]][src[1]]);
q.push(Nw);
// Initialize rows and cols
int N = mat.size(), M = mat[0].size();
// Initialize a boolean matrix
// to keep track of visited cells
bool visited[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
visited[i][j] = false;
}
}
// Initialize the directions
int dir[4][2]
= { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
// Apply BFS
while (!q.empty()) {
Node* curr = q.front();
q.pop();
// If cell is already visited
if (visited[curr->i][curr->j])
continue;
// Mark current node as visited
visited[curr->i][curr->j] = true;
// Return the answer after
// reaching the destination node
if (curr->i == dest[0] && curr->j == dest[1])
return curr->dist;
// Explore neighbors
for (int i = 0; i < 4; i++) {
int x = dir[i][0] + curr->i,
y = dir[i][1] + curr->j;
// If out of bounds or already visited
// or difference in neighbor nodes
// values is greater than K
if (x < 0 || y < 0 || x == N || y == M
|| visited[x][y]
|| abs(curr->val - mat[x][y]) > K)
continue;
// Add current cell into the queue
Node* n
= new Node(x, y, curr->dist + 1, mat[x][y]);
q.push(n);
}
}
// No path exists return -1
return -1;
}
// Driver function
int main()
{
// Initialize the matrix
vector<vector<int> > mat = { { -1, 0, 4, 3 },
{ 6, 5, 7, 8 },
{ 2, 1, 2, 0 } };
int K = 4;
// Source node
int src[] = { 0, 0 };
// Destination node
int dest[] = { 2, 3 };
// Call the function
// and print the answer
cout << (shortestPathLessThanK(mat, K, src, dest));
}
// This code is contributed by Potta Lokesh
Java
// Java implementation for the above approach
import java.io.*;
import java.util.*;
import java.lang.Math;
class GFG {
static class Node {
int dist, i, j, val;
// Constructor
public Node(int i, int j,
int dist, int val)
{
this.i = i;
this.j = j;
this.dist = dist;
this.val = val;
}
}
// Function to find the length of the
// shortest path with neighbor nodes
// value not exceeding K
public static int shortestPathLessThanK(
int[][] mat, int K, int[] src, int[] dest)
{
// Initialize a queue
Queue<Node> q = new LinkedList<>();
// Add the source node
// into the queue
q.add(new Node(src[0], src[1], 0,
mat[src[0]][src[1]]));
// Initialize rows and cols
int N = mat.length,
M = mat[0].length;
// Initialize a boolean matrix
// to keep track of visited cells
boolean[][] visited = new boolean[N][M];
// Initialize the directions
int[][] dir = { { -1, 0 }, { 1, 0 },
{ 0, 1 }, { 0, -1 } };
// Apply BFS
while (!q.isEmpty()) {
Node curr = q.poll();
// If cell is already visited
if (visited[curr.i][curr.j])
continue;
// Mark current node as visited
visited[curr.i][curr.j] = true;
// Return the answer after
// reaching the destination node
if (curr.i == dest[0] && curr.j == dest[1])
return curr.dist;
// Explore neighbors
for (int i = 0; i < 4; i++) {
int x = dir[i][0] + curr.i,
y = dir[i][1] + curr.j;
// If out of bounds or already visited
// or difference in neighbor nodes
// values is greater than K
if (x < 0 || y < 0 || x == N
|| y == M || visited[x][y]
|| Math.abs(curr.val - mat[x][y]) > K)
continue;
// Add current cell into the queue
q.add(new Node(x, y, curr.dist + 1,
mat[x][y]));
}
}
// No path exists return -1
return -1;
}
// Driver code
public static void main(String[] args)
{
// Initialize the matrix
int[][] mat = { { -1, 0, 4, 3 },
{ 6, 5, 7, 8 },
{ 2, 1, 2, 0 } };
int K = 4;
// Source node
int[] src = { 0, 0 };
// Destination node
int[] dest = { 2, 3 };
// Call the function
// and print the answer
System.out.println(
shortestPathLessThanK(mat, K, src, dest));
}
}
C#
// C# implementation for the above approach
using System;
using System.Collections.Generic;
public class GFG {
class Node {
public int dist, i, j, val;
// Constructor
public Node(int i, int j,
int dist, int val)
{
this.i = i;
this.j = j;
this.dist = dist;
this.val = val;
}
}
// Function to find the length of the
// shortest path with neighbor nodes
// value not exceeding K
public static int shortestPathLessThanK(
int[,] mat, int K, int[] src, int[] dest)
{
// Initialize a queue
Queue<Node> q = new Queue<Node>();
// Add the source node
// into the queue
q.Enqueue(new Node(src[0], src[1], 0,
mat[src[0],src[1]]));
// Initialize rows and cols
int N = mat.GetLength(0),
M = mat.GetLength(1);
// Initialize a bool matrix
// to keep track of visited cells
bool[,] visited = new bool[N,M];
// Initialize the directions
int[,] dir = { { -1, 0 }, { 1, 0 },
{ 0, 1 }, { 0, -1 } };
// Apply BFS
while (q.Count!=0) {
Node curr = q.Peek();
q.Dequeue();
// If cell is already visited
if (visited[curr.i,curr.j])
continue;
// Mark current node as visited
visited[curr.i,curr.j] = true;
// Return the answer after
// reaching the destination node
if (curr.i == dest[0] && curr.j == dest[1])
return curr.dist;
// Explore neighbors
for (int i = 0; i < 4; i++) {
int x = dir[i,0] + curr.i,
y = dir[i,1] + curr.j;
// If out of bounds or already visited
// or difference in neighbor nodes
// values is greater than K
if (x < 0 || y < 0 || x == N
|| y == M || visited[x,y]
|| Math.Abs(curr.val - mat[x,y]) > K)
continue;
// Add current cell into the queue
q.Enqueue(new Node(x, y, curr.dist + 1,
mat[x,y]));
}
}
// No path exists return -1
return -1;
}
// Driver code
public static void Main(String[] args)
{
// Initialize the matrix
int[,] mat = { { -1, 0, 4, 3 },
{ 6, 5, 7, 8 },
{ 2, 1, 2, 0 } };
int K = 4;
// Source node
int[] src = { 0, 0 };
// Destination node
int[] dest = { 2, 3 };
// Call the function
// and print the answer
Console.WriteLine(
shortestPathLessThanK(mat, K, src, dest));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript code for the above approach
class Node {
// Constructor
constructor(x, y, d, v) {
this.i = x;
this.j = y;
this.dist = d;
this.val = v;
}
};
// Function to find the length of the
// shortest path with neighbor nodes
// value not exceeding K
function shortestPathLessThanK(mat, K, src, dest) {
// Initialize a queue
let q = [];
// Add the source node
// into the queue
let Nw = new Node(src[0], src[1], 0, mat[src[0]][src[1]]);
q.unshift(Nw);
// Initialize rows and cols
let N = mat.length, M = mat[0].length;
// Initialize a boolean matrix
// to keep track of visited cells
let visited = new Array(N).fill(0).map(() => new Array(M).fill(0));
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
visited[i][j] = false;
}
}
// Initialize the directions
let dir = [[-1, 0], [1, 0], [0, 1], [0, -1]];
// Apply BFS
while (q.length) {
let curr = q[q.length - 1];
q.pop();
// If cell is already visited
if (visited[curr.i][curr.j])
continue;
// Mark current node as visited
visited[curr.i][curr.j] = true;
// Return the answer after
// reaching the destination node
if (curr.i == dest[0] && curr.j == dest[1])
return curr.dist;
// Explore neighbors
for (let i = 0; i < 4; i++) {
let x = dir[i][0] + curr.i,
y = dir[i][1] + curr.j;
// If out of bounds or already visited
// or difference in neighbor nodes
// values is greater than K
if (x < 0 || y < 0 || x == N || y == M
|| visited[x][y]
|| Math.abs(curr.val - mat[x][y]) > K)
continue;
// Add current cell into the queue
let n
= new Node(x, y, curr.dist + 1, mat[x][y]);
q.unshift(n);
}
}
// No path exists return -1
return -1;
}
// Driver function
// Initialize the matrix
let mat = [[-1, 0, 4, 3], [6, 5, 7, 8], [2, 1, 2, 0]];
let K = 4;
// Source node
let src = [0, 0];
// Destination node
let dest = [2, 3];
// Call the function
// and print the answer
document.write(shortestPathLessThanK(mat, K, src, dest));
// This code is contributed by gfgking.
</script>
Producción
7
Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(N * M)