Dada una array MxN donde cada elemento puede ser 0 o 1. Necesitamos encontrar el camino más corto entre una celda de origen dada y una celda de destino. La ruta solo se puede crear a partir de una celda si su valor es 1.
Por ejemplo –
Input:
mat[ROW][COL] = {{1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
{1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
{0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
{1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
{1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }};
Source = {0, 0};
Destination = {3, 4};
Output:
Shortest Path is 11
Método 1: usar el retroceso
La idea es usar recursividad:
- Comience desde la celda de origen dada en la array y explore los cuatro caminos posibles.
- Compruebe si se ha alcanzado el destino o no.
- Explore todos los caminos y retroceda si no se alcanza el destino.
- Y también realice un seguimiento de las celdas visitadas utilizando una array.
Valid Moves are: left: (i, j) ——> (i, j – 1) right: (i, j) ——> (i, j + 1) top: (i, j) ——> (i - 1, j) bottom: (i, j) ——> (i + 1, j )
Implementación:
C++
#include <iostream>
#include <vector>
#include <climits>
#include <cstring>
using namespace std;
// Check if it is possible to go to (x, y) from the current position. The
// function returns false if the cell has value 0 or already visited
bool isSafe(vector<vector<int>> &mat, vector<vector<bool>> &visited, int x, int y)
{
return (x >= 0 && x < mat.size() && y >= 0 && y < mat[0].size()) &&
mat[x][y] == 1 && !visited[x][y];
}
void findShortestPath(vector<vector<int>> &mat, vector<vector<bool>> &visited,
int i, int j, int x, int y, int &min_dist, int dist){
if (i == x && j == y){
min_dist = min(dist, min_dist);
return;
}
// set (i, j) cell as visited
visited[i][j] = true;
// go to the bottom cell
if (isSafe(mat, visited, i + 1, j)) {
findShortestPath(mat, visited, i + 1, j, x, y, min_dist, dist + 1);
}
// go to the right cell
if (isSafe(mat, visited, i, j + 1)) {
findShortestPath(mat, visited, i, j + 1, x, y, min_dist, dist + 1);
}
// go to the top cell
if (isSafe(mat, visited, i - 1, j)) {
findShortestPath(mat, visited, i - 1, j, x, y, min_dist, dist + 1);
}
// go to the left cell
if (isSafe(mat, visited, i, j - 1)) {
findShortestPath(mat, visited, i, j - 1, x, y, min_dist, dist + 1);
}
// backtrack: remove (i, j) from the visited matrix
visited[i][j] = false;
}
// Wrapper over findShortestPath() function
int findShortestPathLength(vector<vector<int>> &mat, pair<int, int> &src,
pair<int, int> &dest){
if (mat.size() == 0 || mat[src.first][src.second] == 0 ||
mat[dest.first][dest.second] == 0)
return -1;
int row = mat.size();
int col = mat[0].size();
// construct an `M × N` matrix to keep track of visited cells
vector<vector<bool>> visited;
visited.resize(row, vector<bool>(col));
int dist = INT_MAX;
findShortestPath(mat, visited, src.first, src.second, dest.first, dest.second,
dist, 0);
if (dist != INT_MAX)
return dist;
return -1;
}
int main()
{
vector<vector<int>> mat =
{{1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
{1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
{0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
{1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
{1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }};
pair<int, int> src = make_pair(0, 0);
pair<int, int> dest = make_pair(3, 4);
int dist = findShortestPathLength(mat, src, dest);
if (dist != -1)
cout << "Shortest Path is " << dist;
else
cout << "Shortest Path doesn't exist";
return 0;
}
Java
// Java implementation of the code
import java.util.*;
class GFG {
static boolean[][] visited;
// Check if it is possible to go to (x, y) from the
// current position. The function returns false if the
// cell has value 0 or already visited
static boolean isSafe(int[][] mat, boolean[][] visited,
int x, int y)
{
return (x >= 0 && x < mat.length && y >= 0
&& y < mat[0].length && mat[x][y] == 1
&& !visited[x][y]);
}
static int findShortestPath(int[][] mat, int i, int j,
int x, int y, int min_dist,
int dist)
{
if (i == x && j == y) {
min_dist = Math.min(dist, min_dist);
return min_dist;
}
// set (i, j) cell as visited
visited[i][j] = true;
// go to the bottom cell
if (isSafe(mat, visited, i + 1, j)) {
min_dist = findShortestPath(mat, i + 1, j, x, y,
min_dist, dist + 1);
}
// go to the right cell
if (isSafe(mat, visited, i, j + 1)) {
min_dist = findShortestPath(mat, i, j + 1, x, y,
min_dist, dist + 1);
}
// go to the top cell
if (isSafe(mat, visited, i - 1, j)) {
min_dist = findShortestPath(mat, i - 1, j, x, y,
min_dist, dist + 1);
}
// go to the left cell
if (isSafe(mat, visited, i, j - 1)) {
min_dist = findShortestPath(mat, i, j - 1, x, y,
min_dist, dist + 1);
}
// backtrack: remove (i, j) from the visited matrix
visited[i][j] = false;
return min_dist;
}
// Wrapper over findShortestPath() function
static int findShortestPathLength(int[][] mat,
int[] src, int[] dest)
{
if (mat.length == 0 || mat[src[0]][src[1]] == 0
|| mat[dest[0]][dest[1]] == 0)
return -1;
int row = mat.length;
int col = mat[0].length;
// construct an `M × N` matrix to keep track of
// visited cells
visited = new boolean[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++)
visited[i][j] = false;
}
int dist = Integer.MAX_VALUE;
dist = findShortestPath(mat, src[0], src[1],
dest[0], dest[1], dist, 0);
if (dist != Integer.MAX_VALUE)
return dist;
return -1;
}
// Driver code
public static void main(String[] args)
{
int[][] mat = new int[][] {
{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
{ 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }
};
int[] src = { 0, 0 };
int[] dest = { 3, 4 };
int dist = findShortestPathLength(mat, src, dest);
if (dist != -1)
System.out.print("Shortest Path is " + dist);
else
System.out.print("Shortest Path doesn't exist");
}
}
// This code is contributed by phasing17
Python3
# Python3 code to implement the approach
import sys
# User defined Pair class
class Pair:
def __init__(self, x, y):
self.first = x
self.second = y
# Check if it is possible to go to (x, y) from the current
# position. The function returns false if the cell has
# value 0 or already visited
def isSafe(mat, visited, x, y):
return (x >= 0 and x < len(mat) and y >= 0 and y < len(mat[0]) and mat[x][y] == 1 and (not visited[x][y]))
def findShortestPath(mat, visited, i, j, x, y, min_dist, dist):
if (i == x and j == y):
min_dist = min(dist, min_dist)
return min_dist
# set (i, j) cell as visited
visited[i][j] = True
# go to the bottom cell
if (isSafe(mat, visited, i + 1, j)):
min_dist = findShortestPath(
mat, visited, i + 1, j, x, y, min_dist, dist + 1)
# go to the right cell
if (isSafe(mat, visited, i, j + 1)):
min_dist = findShortestPath(
mat, visited, i, j + 1, x, y, min_dist, dist + 1)
# go to the top cell
if (isSafe(mat, visited, i - 1, j)):
min_dist = findShortestPath(
mat, visited, i - 1, j, x, y, min_dist, dist + 1)
# go to the left cell
if (isSafe(mat, visited, i, j - 1)):
min_dist = findShortestPath(
mat, visited, i, j - 1, x, y, min_dist, dist + 1)
# backtrack: remove (i, j) from the visited matrix
visited[i][j] = False
return min_dist
# Wrapper over findShortestPath() function
def findShortestPathLength(mat, src, dest):
if (len(mat) == 0 or mat[src.first][src.second] == 0
or mat[dest.first][dest.second] == 0):
return -1
row = len(mat)
col = len(mat[0])
# construct an `M × N` matrix to keep track of visited
# cells
visited = []
for i in range(row):
visited.append([None for _ in range(col)])
dist = sys.maxsize
dist = findShortestPath(mat, visited, src.first,
src.second, dest.first, dest.second, dist, 0)
if (dist != sys.maxsize):
return dist
return -1
# Driver code
mat = [[1, 0, 1, 1, 1, 1, 0, 1, 1, 1],
[1, 0, 1, 0, 1, 1, 1, 0, 1, 1],
[1, 1, 1, 0, 1, 1, 0, 1, 0, 1],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 1],
[1, 1, 1, 0, 1, 1, 1, 0, 1, 0],
[1, 0, 1, 1, 1, 1, 0, 1, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 1, 0, 1, 1, 1],
[1, 1, 0, 0, 0, 0, 1, 0, 0, 1]
]
src = Pair(0, 0)
dest = Pair(3, 4)
dist = findShortestPathLength(mat, src, dest)
if (dist != -1):
print("Shortest Path is", dist)
else:
print("Shortest Path doesn't exist")
# This code is contributed by phasing17
Javascript
// JavaScript code to implement the approach
// User defined Pair class
class Pair {
constructor(x, y)
{
this.first = x;
this.second = y;
}
}
// Check if it is possible to go to (x, y) from the current
// position. The function returns false if the cell has
// value 0 or already visited
function isSafe(mat, visited, x, y)
{
return (x >= 0 && x < mat.length && y >= 0
&& y < mat[0].length && mat[x][y] == 1
&& !visited[x][y]);
}
function findShortestPath(mat, visited, i, j, x, y,
min_dist, dist)
{
if (i == x && j == y) {
min_dist = Math.min(dist, min_dist);
return min_dist;
}
// set (i, j) cell as visited
visited[i][j] = true;
// go to the bottom cell
if (isSafe(mat, visited, i + 1, j)) {
min_dist
= findShortestPath(mat, visited, i + 1, j, x, y,
min_dist, dist + 1);
}
// go to the right cell
if (isSafe(mat, visited, i, j + 1)) {
min_dist
= findShortestPath(mat, visited, i, j + 1, x, y,
min_dist, dist + 1);
}
// go to the top cell
if (isSafe(mat, visited, i - 1, j)) {
min_dist
= findShortestPath(mat, visited, i - 1, j, x, y,
min_dist, dist + 1);
}
// go to the left cell
if (isSafe(mat, visited, i, j - 1)) {
min_dist
= findShortestPath(mat, visited, i, j - 1, x, y,
min_dist, dist + 1);
}
// backtrack: remove (i, j) from the visited matrix
visited[i][j] = false;
return min_dist;
}
// Wrapper over findShortestPath() function
function findShortestPathLength(mat, src, dest)
{
if (mat.length == 0 || mat[src.first][src.second] == 0
|| mat[dest.first][dest.second] == 0)
return -1;
let row = mat.length;
let col = mat[0].length;
// construct an `M × N` matrix to keep track of visited
// cells
let visited = [];
for (var i = 0; i < row; i++)
visited.push(new Array(col));
let dist = Number.MAX_SAFE_INTEGER;
dist = findShortestPath(mat, visited, src.first,
src.second, dest.first,
dest.second, dist, 0);
if (dist != Number.MAX_SAFE_INTEGER)
return dist;
return -1;
}
// Driver code
let mat = [
[ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 ],
[ 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 ],
[ 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 ],
[ 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 ],
[ 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 ],
[ 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 ],
[ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 ],
[ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 ],
[ 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 ]
];
let src = new Pair(0, 0);
let dest = new Pair(3, 4);
let dist = findShortestPathLength(mat, src, dest);
if (dist != -1)
console.log("Shortest Path is " + dist);
else
console.log("Shortest Path doesn't exist");
// This code is contributed by phasing17
Producción
Shortest Path is 11
Complejidad de tiempo: O(4^MN)
Complejidad de espacio : O(MN)
Método 2: Usar BFS
La idea está inspirada en el algoritmo de Lee y usa BFS.
- Partimos de la celda fuente y llamamos al procedimiento BFS.
- Mantenemos una cola para almacenar las coordenadas de la array e inicializarla con la celda de origen.
- También mantenemos una array booleana visitada del mismo tamaño que nuestra array de entrada e inicializamos todos sus elementos en falso.
- Hacemos LOOP hasta que la cola no esté vacía
- Eliminar la celda frontal de la cola
- Regresar si se han alcanzado las coordenadas de destino.
- Para cada una de sus cuatro celdas adyacentes, si el valor es 1 y aún no han sido visitadas, las encolamos en la cola y también las marcamos como visitadas.
Tenga en cuenta que BFS funciona aquí porque no considera una sola ruta a la vez. Considera todos los caminos que parten del origen y avanza una unidad en todos esos caminos al mismo tiempo, lo que asegura que la primera vez que se visita el destino, sea el camino más corto.
A continuación se muestra la implementación de la idea:
Implementación:
C++
// C++ program to find the shortest path between
// a given source cell to a destination cell.
#include <bits/stdc++.h>
using namespace std;
#define ROW 9
#define COL 10
//To store matrix cell coordinates
struct Point
{
int x;
int y;
};
// A Data Structure for queue used in BFS
struct queueNode
{
Point pt; // The coordinates of a cell
int dist; // cell's distance of from the source
};
// check whether given cell (row, col) is a valid
// cell or not.
bool isValid(int row, int col)
{
// return true if row number and column number
// is in range
return (row >= 0) && (row < ROW) &&
(col >= 0) && (col < COL);
}
// These arrays are used to get row and column
// numbers of 4 neighbours of a given cell
int rowNum[] = {-1, 0, 0, 1};
int colNum[] = {0, -1, 1, 0};
// function to find the shortest path between
// a given source cell to a destination cell.
int BFS(int mat[][COL], Point src, Point dest)
{
// check source and destination cell
// of the matrix have value 1
if (!mat[src.x][src.y] || !mat[dest.x][dest.y])
return -1;
bool visited[ROW][COL];
memset(visited, false, sizeof visited);
// Mark the source cell as visited
visited[src.x][src.y] = true;
// Create a queue for BFS
queue<queueNode> q;
// Distance of source cell is 0
queueNode s = {src, 0};
q.push(s); // Enqueue source cell
// Do a BFS starting from source cell
while (!q.empty())
{
queueNode curr = q.front();
Point pt = curr.pt;
// If we have reached the destination cell,
// we are done
if (pt.x == dest.x && pt.y == dest.y)
return curr.dist;
// Otherwise dequeue the front
// cell in the queue
// and enqueue its adjacent cells
q.pop();
for (int i = 0; i < 4; i++)
{
int row = pt.x + rowNum[i];
int col = pt.y + colNum[i];
// if adjacent cell is valid, has path and
// not visited yet, enqueue it.
if (isValid(row, col) && mat[row][col] &&
!visited[row][col])
{
// mark cell as visited and enqueue it
visited[row][col] = true;
queueNode Adjcell = { {row, col},
curr.dist + 1 };
q.push(Adjcell);
}
}
}
// Return -1 if destination cannot be reached
return -1;
}
// Driver program to test above function
int main()
{
int mat[ROW][COL] =
{
{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
{ 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }
};
Point source = {0, 0};
Point dest = {3, 4};
int dist = BFS(mat, source, dest);
if (dist != -1)
cout << "Shortest Path is " << dist ;
else
cout << "Shortest Path doesn't exist";
return 0;
}
Java
// Java program to find the shortest
// path between a given source cell
// to a destination cell.
import java.util.*;
class GFG
{
static int ROW = 9;
static int COL = 10;
// To store matrix cell coordinates
static class Point
{
int x;
int y;
public Point(int x, int y)
{
this.x = x;
this.y = y;
}
};
// A Data Structure for queue used in BFS
static class queueNode
{
Point pt; // The coordinates of a cell
int dist; // cell's distance of from the source
public queueNode(Point pt, int dist)
{
this.pt = pt;
this.dist = dist;
}
};
// check whether given cell (row, col)
// is a valid cell or not.
static boolean isValid(int row, int col)
{
// return true if row number and
// column number is in range
return (row >= 0) && (row < ROW) &&
(col >= 0) && (col < COL);
}
// These arrays are used to get row and column
// numbers of 4 neighbours of a given cell
static int rowNum[] = {-1, 0, 0, 1};
static int colNum[] = {0, -1, 1, 0};
// function to find the shortest path between
// a given source cell to a destination cell.
static int BFS(int mat[][], Point src,
Point dest)
{
// check source and destination cell
// of the matrix have value 1
if (mat[src.x][src.y] != 1 ||
mat[dest.x][dest.y] != 1)
return -1;
boolean [][]visited = new boolean[ROW][COL];
// Mark the source cell as visited
visited[src.x][src.y] = true;
// Create a queue for BFS
Queue<queueNode> q = new LinkedList<>();
// Distance of source cell is 0
queueNode s = new queueNode(src, 0);
q.add(s); // Enqueue source cell
// Do a BFS starting from source cell
while (!q.isEmpty())
{
queueNode curr = q.peek();
Point pt = curr.pt;
// If we have reached the destination cell,
// we are done
if (pt.x == dest.x && pt.y == dest.y)
return curr.dist;
// Otherwise dequeue the front cell
// in the queue and enqueue
// its adjacent cells
q.remove();
for (int i = 0; i < 4; i++)
{
int row = pt.x + rowNum[i];
int col = pt.y + colNum[i];
// if adjacent cell is valid, has path
// and not visited yet, enqueue it.
if (isValid(row, col) &&
mat[row][col] == 1 &&
!visited[row][col])
{
// mark cell as visited and enqueue it
visited[row][col] = true;
queueNode Adjcell = new queueNode
(new Point(row, col),
curr.dist + 1 );
q.add(Adjcell);
}
}
}
// Return -1 if destination cannot be reached
return -1;
}
// Driver Code
public static void main(String[] args)
{
int mat[][] = {{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
{ 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }};
Point source = new Point(0, 0);
Point dest = new Point(3, 4);
int dist = BFS(mat, source, dest);
if (dist != -1)
System.out.println("Shortest Path is " + dist);
else
System.out.println("Shortest Path doesn't exist");
}
}
// This code is contributed by PrinciRaj1992
Python
# Python program to find the shortest
# path between a given source cell
# to a destination cell.
from collections import deque
ROW = 9
COL = 10
# To store matrix cell coordinates
class Point:
def __init__(self,x: int, y: int):
self.x = x
self.y = y
# A data structure for queue used in BFS
class queueNode:
def __init__(self,pt: Point, dist: int):
self.pt = pt # The coordinates of the cell
self.dist = dist # Cell's distance from the source
# Check whether given cell(row,col)
# is a valid cell or not
def isValid(row: int, col: int):
return (row >= 0) and (row < ROW) and
(col >= 0) and (col < COL)
# These arrays are used to get row and column
# numbers of 4 neighbours of a given cell
rowNum = [-1, 0, 0, 1]
colNum = [0, -1, 1, 0]
# Function to find the shortest path between
# a given source cell to a destination cell.
def BFS(mat, src: Point, dest: Point):
# check source and destination cell
# of the matrix have value 1
if mat[src.x][src.y]!=1 or mat[dest.x][dest.y]!=1:
return -1
visited = [[False for i in range(COL)]
for j in range(ROW)]
# Mark the source cell as visited
visited[src.x][src.y] = True
# Create a queue for BFS
q = deque()
# Distance of source cell is 0
s = queueNode(src,0)
q.append(s) # Enqueue source cell
# Do a BFS starting from source cell
while q:
curr = q.popleft() # Dequeue the front cell
# If we have reached the destination cell,
# we are done
pt = curr.pt
if pt.x == dest.x and pt.y == dest.y:
return curr.dist
# Otherwise enqueue its adjacent cells
for i in range(4):
row = pt.x + rowNum[i]
col = pt.y + colNum[i]
# if adjacent cell is valid, has path
# and not visited yet, enqueue it.
if (isValid(row,col) and
mat[row][col] == 1 and
not visited[row][col]):
visited[row][col] = True
Adjcell = queueNode(Point(row,col),
curr.dist+1)
q.append(Adjcell)
# Return -1 if destination cannot be reached
return -1
# Driver code
def main():
mat = [[ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 ],
[ 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 ],
[ 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 ],
[ 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 ],
[ 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 ],
[ 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 ],
[ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 ],
[ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 ],
[ 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 ]]
source = Point(0,0)
dest = Point(3,4)
dist = BFS(mat,source,dest)
if dist!=-1:
print("Shortest Path is",dist)
else:
print("Shortest Path doesn't exist")
main()
# This code is contributed by stutipathak31jan
C#
// C# program to find the shortest
// path between a given source cell
// to a destination cell.
using System;
using System.Collections.Generic;
class GFG
{
static int ROW = 9;
static int COL = 10;
// To store matrix cell coordinates
public class Point
{
public int x;
public int y;
public Point(int x, int y)
{
this.x = x;
this.y = y;
}
};
// A Data Structure for queue used in BFS
public class queueNode
{
// The coordinates of a cell
public Point pt;
// cell's distance of from the source
public int dist;
public queueNode(Point pt, int dist)
{
this.pt = pt;
this.dist = dist;
}
};
// check whether given cell (row, col)
// is a valid cell or not.
static bool isValid(int row, int col)
{
// return true if row number and
// column number is in range
return (row >= 0) && (row < ROW) &&
(col >= 0) && (col < COL);
}
// These arrays are used to get row and column
// numbers of 4 neighbours of a given cell
static int []rowNum = {-1, 0, 0, 1};
static int []colNum = {0, -1, 1, 0};
// function to find the shortest path between
// a given source cell to a destination cell.
static int BFS(int [,]mat, Point src,
Point dest)
{
// check source and destination cell
// of the matrix have value 1
if (mat[src.x, src.y] != 1 ||
mat[dest.x, dest.y] != 1)
return -1;
bool [,]visited = new bool[ROW, COL];
// Mark the source cell as visited
visited[src.x, src.y] = true;
// Create a queue for BFS
Queue<queueNode> q = new Queue<queueNode>();
// Distance of source cell is 0
queueNode s = new queueNode(src, 0);
q.Enqueue(s); // Enqueue source cell
// Do a BFS starting from source cell
while (q.Count != 0)
{
queueNode curr = q.Peek();
Point pt = curr.pt;
// If we have reached the destination cell,
// we are done
if (pt.x == dest.x && pt.y == dest.y)
return curr.dist;
// Otherwise dequeue the front cell
// in the queue and enqueue
// its adjacent cells
q.Dequeue();
for (int i = 0; i < 4; i++)
{
int row = pt.x + rowNum[i];
int col = pt.y + colNum[i];
// if adjacent cell is valid, has path
// and not visited yet, enqueue it.
if (isValid(row, col) &&
mat[row, col] == 1 &&
!visited[row, col])
{
// mark cell as visited and enqueue it
visited[row, col] = true;
queueNode Adjcell = new queueNode
(new Point(row, col),
curr.dist + 1 );
q.Enqueue(Adjcell);
}
}
}
// Return -1 if destination cannot be reached
return -1;
}
// Driver Code
public static void Main(String[] args)
{
int [,]mat = {{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
{ 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }};
Point source = new Point(0, 0);
Point dest = new Point(3, 4);
int dist = BFS(mat, source, dest);
if (dist != -1)
Console.WriteLine("Shortest Path is " + dist);
else
Console.WriteLine("Shortest Path doesn't exist");
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to find the shortest
// path between a given source cell
// to a destination cell.
const ROW = 9
const COL = 10
// To store matrix cell coordinates
class Point{
constructor(x, y){
this.x = x
this.y = y
}
}
// A data structure for queue used in BFS
class queueNode{
constructor(pt, dist){
this.pt = pt // The coordinates of the cell
this.dist = dist // Cell's distance from the source
}
}
// Check whether given cell(row,col)
// is a valid cell or not
function isValid(row, col){
return (row >= 0) && (row < ROW) &&
(col >= 0) && (col < COL)
}
// These arrays are used to get row and column
// numbers of 4 neighbours of a given cell
let rowNum = [-1, 0, 0, 1]
let colNum = [0, -1, 1, 0]
// Function to find the shortest path between
// a given source cell to a destination cell.
function BFS(mat, src, dest){
// check source and destination cell
// of the matrix have value 1
if(mat[src.x][src.y]!=1 || mat[dest.x][dest.y]!=1)
return -1
let visited = new Array(ROW).fill(false).map(()=>new Array(COL).fill(false));
// Mark the source cell as visited
visited[src.x][src.y] = true
// Create a queue for BFS
let q = []
// Distance of source cell is 0
let s = new queueNode(src,0)
q.push(s) // Enqueue source cell
// Do a BFS starting from source cell
while(q){
let curr = q.shift() // Dequeue the front cell
// If we have reached the destination cell,
// we are done
let pt = curr.pt
if(pt.x == dest.x && pt.y == dest.y)
return curr.dist
// Otherwise enqueue its adjacent cells
for(let i=0;i<4;i++){
let row = pt.x + rowNum[i]
let col = pt.y + colNum[i]
// if adjacent cell is valid, has path
// and not visited yet, enqueue it.
if (isValid(row,col) && mat[row][col] == 1 && !visited[row][col]){
visited[row][col] = true
let Adjcell = new queueNode(new Point(row,col),
curr.dist+1)
q.push(Adjcell)
}
}
}
// Return -1 if destination cannot be reached
return -1
}
// Driver code
function main(){
let mat = [[ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 ],
[ 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 ],
[ 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 ],
[ 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 ],
[ 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 ],
[ 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 ],
[ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 ],
[ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 ],
[ 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 ]]
let source = new Point(0,0)
let dest = new Point(3,4)
let dist = BFS(mat,source,dest)
if(dist!=-1)
document.write("Shortest Path is",dist,"</br>")
else
document.write("Shortest Path doesn't exist","</br>")
}
main()
// This code is contributed by shinjanpatra
</script>
Producción
Shortest Path is 11
La complejidad de tiempo esperada es O(MN)
Este artículo es una contribución de Aditya Goel . 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