123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121
#include <bits/stdc++.h>
using namespace std;
class Solution{
private:
// Delta row and column array
vector<int> delRow = {-1, 0, 1, 0};
vector<int> delCol = {0, -1, 0, 1};
// Function to check if a cell is valid
bool isValid(int &row, int &col,
int &n, int &m) {
// Return false if the cell is invalid
if(row < 0 || row >= n) return false;
if(col < 0 || col >= m) return false;
// Return true if the cell is valid
return true;
}
public:
/* Function to determine the shortest distance
between source and destination */
int shortestPath(vector<vector<int>> &grid, pair<int, int> source,
pair<int, int> destination) {
// Edge Case
if (source.first == destination.first &&
source.second == destination.second)
return 0;
/* Queue data structure to store the pairs of the
form: {dist, {coordinates of cell}} */
queue<pair<int, pair<int, int>>> q;
// Dimensions of grid
int n = grid.size();
int m = grid[0].size();
// Distance matrix
vector<vector<int>> dist(n, vector<int>(m, 1e9));
// Distane of source from itself is zero
dist[source.first][source.second] = 0;
// Add the surce to queue
q.push({0, {source.first, source.second}});
// Until the queue is empty
while (!q.empty()) {
// Get the element
auto it = q.front();
q.pop();
int dis = it.first; // Distance
int row = it.second.first; // Row of cell
int col = it.second.second; // Column of cell
// Iterate through all the neighbors
for (int i = 0; i < 4; i++){
// Coordinates of the new cell
int newRow = row + delRow[i];
int newCol = col + delCol[i];
/* Checking the validity of the cell and
updating if a shorter distance is found */
if (isValid(newRow, newCol, n, m) &&
grid[newRow][newCol] == 1 &&
dis + 1 < dist[newRow][newCol]) {
// Update the distance
dist[newRow][newCol] = 1 + dis;
// Return the distance is the destination is reached
if (newRow == destination.first &&
newCol == destination.second)
return dis + 1;
// Add the new cell to queue
q.push({1 + dis, {newRow, newCol}});
}
}
}
// If no path is found from source to destination
return -1;
}
};
int main() {
pair<int, int> source, destination;
source.first = 0;
source.second = 1;
destination.first = 2;
destination.second = 2;
vector<vector<int>> grid = {
{1, 1, 1, 1},
{1, 1, 0, 1},
{1, 1, 1, 1},
{1, 1, 0, 0},
{1, 0, 0, 1}
};
/* Creating an instance of
Solution class */
Solution sol;
/* Function call to determine the shortest
distance between source and destination */
int ans = sol.shortestPath(grid, source, destination);
cout << "The shortest distance from the source to destination is: " << ans;
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115
import java.util.*;
class Solution {
// Delta row and column array
private int[] delRow = {-1, 0, 1, 0};
private int[] delCol = {0, -1, 0, 1};
// Function to check if a cell is valid
private boolean isValid(int row, int col,
int n, int m) {
// Return false if the cell is invalid
if (row < 0 || row >= n) return false;
if (col < 0 || col >= m) return false;
// Return true if the cell is valid
return true;
}
/* Function to determine the shortest distance
between source and destination */
public int shortestPath(int[][] grid, int[] source,
int[] destination) {
// Edge Case
if (source[0] == destination[0] &&
source[1] == destination[1])
return 0;
/* Queue data structure to store the pairs of the
form: {dist, {coordinates of cell}} */
Queue<int[]> q = new LinkedList<>();
// Dimensions of grid
int n = grid.length;
int m = grid[0].length;
// Distance matrix
int[][] dist = new int[n][m];
for (int[] row : dist) {
Arrays.fill(row, Integer.MAX_VALUE);
}
// Distance of source from itself is zero
dist[source[0]][source[1]] = 0;
// Add the source to queue
q.add(new int[]{0, source[0], source[1]});
// Until the queue is empty
while (!q.isEmpty()) {
// Get the element
int[] it = q.poll();
int dis = it[0]; // Distance
int row = it[1]; // Row of cell
int col = it[2]; // Column of cell
// Iterate through all the neighbors
for (int i = 0; i < 4; i++) {
// Coordinates of the new cell
int newRow = row + delRow[i];
int newCol = col + delCol[i];
/* Checking the validity of the cell and
updating if a shorter distance is found */
if (isValid(newRow, newCol, n, m) &&
grid[newRow][newCol] == 1 &&
dis + 1 < dist[newRow][newCol]) {
// Update the distance
dist[newRow][newCol] = 1 + dis;
/* Return the distance if the
destination is reached */
if (newRow == destination[0] &&
newCol == destination[1])
return dis + 1;
// Add the new cell to queue
q.add(new int[]{1 + dis, newRow, newCol});
}
}
}
// If no path is found from source to destination
return -1;
}
public static void main(String[] args) {
int[] source = {0, 1};
int[] destination = {2, 2};
int[][] grid = {
{1, 1, 1, 1},
{1, 1, 0, 1},
{1, 1, 1, 1},
{1, 1, 0, 0},
{1, 0, 0, 1}
};
/* Creating an instance of
Solution class */
Solution sol = new Solution();
/* Function call to determine the shortest
distance between source and destination */
int ans = sol.shortestPath(grid, source, destination);
System.out.println("The shortest distance from the source to destination is: " + ans);
}
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091
from collections import deque
class Solution:
# Delta row and column array
delRow = [-1, 0, 1, 0]
delCol = [0, -1, 0, 1]
# Function to check if a cell is valid
def isValid(self, row, col, n, m):
# Return false if the cell is invalid
if row < 0 or row >= n: return False
if col < 0 or col >= m: return False
# Return true if the cell is valid
return True
# Function to determine the shortest distance
# between source and destination
def shortestPath(self, grid, source, destination):
# Edge Case
if source == destination:
return 0
# Queue data structure to store the pairs of the
# form: {dist, {coordinates of cell}}
q = deque()
# Dimensions of grid
n = len(grid)
m = len(grid[0])
# Distance matrix
dist = [[float('inf')] * m for _ in range(n)]
# Distance of source from itself is zero
dist[source[0]][source[1]] = 0
# Add the source to queue
q.append((0, source[0], source[1]))
# Until the queue is empty
while q:
# Get the element
dis, row, col = q.popleft()
# Iterate through all the neighbors
for i in range(4):
# Coordinates of the new cell
newRow = row + self.delRow[i]
newCol = col + self.delCol[i]
# Checking the validity of the cell and
# updating if a shorter distance is found
if (self.isValid(newRow, newCol, n, m) and
grid[newRow][newCol] == 1 and
dis + 1 < dist[newRow][newCol]):
# Update the distance
dist[newRow][newCol] = 1 + dis
# Return the distance if the destination is reached
if (newRow, newCol) == destination:
return dis + 1
# Add the new cell to queue
q.append((1 + dis, newRow, newCol))
# If no path is found from source to destination
return -1
if __name__ == "__main__":
source = (0, 1)
destination = (2, 2)
grid = [
[1, 1, 1, 1],
[1, 1, 0, 1],
[1, 1, 1, 1],
[1, 1, 0, 0],
[1, 0, 0, 1]
]
# Creating an instance of
# Solution class
sol = Solution()
# Function call to determine the shortest
# distance between source and destination
ans = sol.shortestPath(grid, source, destination)
print(f"The shortest distance from the source to destination is: {ans}")
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105
class Solution {
// Delta row and column array
delRow = [-1, 0, 1, 0];
delCol = [0, -1, 0, 1];
// Function to check if a cell is valid
isValid(row, col, n, m) {
// Return false if the cell is invalid
if (row < 0 || row >= n) return false;
if (col < 0 || col >= m) return false;
// Return true if the cell is valid
return true;
}
// Function to determine the shortest distance
// between source and destination
shortestPath(grid, source, destination) {
// Edge Case
if (source[0] === destination[0] &&
source[1] === destination[1])
return 0;
// Queue data structure to store the pairs of the
// form: {dist, {coordinates of cell}}
const q = [];
// Dimensions of grid
const n = grid.length;
const m = grid[0].length;
// Distance matrix
const dist = Array.from(
{ length: n },
() => Array(m).fill(Infinity)
);
// Distance of source from itself is zero
dist[source[0]][source[1]] = 0;
// Add the source to queue
q.push([0, source[0], source[1]]);
// Until the queue is empty
while (q.length > 0) {
// Get the element
const [dis, row, col] = q.shift();
// Iterate through all the neighbors
for (let i = 0; i < 4; i++) {
// Coordinates of the new cell
const newRow = row + this.delRow[i];
const newCol = col + this.delCol[i];
// Checking the validity of the cell and
// updating if a shorter distance is found
if (this.isValid(newRow, newCol, n, m) &&
grid[newRow][newCol] === 1 &&
dis + 1 < dist[newRow][newCol]) {
// Update the distance
dist[newRow][newCol] = 1 + dis;
// Return the distance if the destination is reached
if (newRow === destination[0] &&
newCol === destination[1])
return dis + 1;
// Add the new cell to queue
q.push([1 + dis, newRow, newCol]);
}
}
}
// If no path is found from source to destination
return -1;
}
}
const main = () => {
const source = [0, 1];
const destination = [2, 2];
const grid = [
[1, 1, 1, 1],
[1, 1, 0, 1],
[1, 1, 1, 1],
[1, 1, 0, 0],
[1, 0, 0, 1]
];
// Creating an instance of
// Solution class
const sol = new Solution();
// Function call to determine the shortest
// distance between source and destination
const ans = sol.shortestPath(grid, source, destination);
console.log(`The shortest distance from the source to destination is: ${ans}`);
};
main();
