Given a matrix of N*M order. Find the shortest distance from a source cell to a destination cell, traversing through limited cells only. Also you can move only up, down, left and right. If found output the distance else -1.
s represents ‘source’
d represents ‘destination’
* represents cell you can travel
0 represents cell you can not travel
This problem is meant for single source and destination.
Examples:
Input : {'0', '*', '0', 's'},
{'*', '0', '*', '*'},
{'0', '*', '*', '*'},
{'d', '*', '*', '*'}
Output : 6
Input : {'0', '*', '0', 's'},
{'*', '0', '*', '*'},
{'0', '*', '*', '*'},
{'d', '0', '0', '0'}
Output : -1
The idea is to BFS (breadth first search) on matrix cells. Note that we can always use BFS to find shortest path if graph is unweighted.
- Store each cell as a node with their row, column values and distance from source cell.
- Start BFS with source cell.
- Make a visited array with all having “false” values except ‘0’cells which are assigned “true” values as they can not be traversed.
- Keep updating distance from source value in each move.
- Return distance when destination is met, else return -1 (no path exists in between source and destination).
CPP
// C++ Code implementation for above problem#include <bits/stdc++.h>using namespace std;#define N 4#define M 4// QItem for current location and distance// from source locationclass QItem {public: int row; int col; int dist; QItem(int x, int y, int w) : row(x), col(y), dist(w) { }};int minDistance(char grid[N][M]){ QItem source(0, 0, 0); // To keep track of visited QItems. Marking // blocked cells as visited. bool visited[N][M]; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (grid[i][j] == '0') visited[i][j] = true; else visited[i][j] = false; // Finding source if (grid[i][j] == 's') { source.row = i; source.col = j; } } } // applying BFS on matrix cells starting from source queue<QItem> q; q.push(source); visited[source.row][source.col] = true; while (!q.empty()) { QItem p = q.front(); q.pop(); // Destination found; if (grid[p.row][p.col] == 'd') return p.dist; // moving up if (p.row - 1 >= 0 && visited[p.row - 1][p.col] == false) { q.push(QItem(p.row - 1, p.col, p.dist + 1)); visited[p.row - 1][p.col] = true; } // moving down if (p.row + 1 < N && visited[p.row + 1][p.col] == false) { q.push(QItem(p.row + 1, p.col, p.dist + 1)); visited[p.row + 1][p.col] = true; } // moving left if (p.col - 1 >= 0 && visited[p.row][p.col - 1] == false) { q.push(QItem(p.row, p.col - 1, p.dist + 1)); visited[p.row][p.col - 1] = true; } // moving right if (p.col + 1 < M && visited[p.row][p.col + 1] == false) { q.push(QItem(p.row, p.col + 1, p.dist + 1)); visited[p.row][p.col + 1] = true; } } return -1;}// Driver codeint main(){ char grid[N][M] = { { '0', '*', '0', 's' }, { '*', '0', '*', '*' }, { '0', '*', '*', '*' }, { 'd', '*', '*', '*' } }; cout << minDistance(grid); return 0;} |
Java
/*package whatever //do not write package name here */// Java Code implementation for above problemimport java.util.LinkedList;import java.util.Queue;import java.util.Scanner;// QItem for current location and distance// from source locationclass QItem { int row; int col; int dist; public QItem(int row, int col, int dist) { this.row = row; this.col = col; this.dist = dist; }}public class Maze { private static int minDistance(char[][] grid) { QItem source = new QItem(0, 0, 0); // To keep track of visited QItems. Marking // blocked cells as visited. firstLoop: for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[i].length; j++) { // Finding source if (grid[i][j] == 's') { source.row = i; source.col = j; break firstLoop; } } } // applying BFS on matrix cells starting from source Queue<QItem> queue = new LinkedList<>(); queue.add(new QItem(source.row, source.col, 0)); boolean[][] visited = new boolean[grid.length][grid[0].length]; visited[source.row][source.col] = true; while (queue.isEmpty() == false) { QItem p = queue.remove(); // Destination found; if (grid[p.row][p.col] == 'd') return p.dist; // moving up if (isValid(p.row - 1, p.col, grid, visited)) { queue.add(new QItem(p.row - 1, p.col, p.dist + 1)); visited[p.row - 1][p.col] = true; } // moving down if (isValid(p.row + 1, p.col, grid, visited)) { queue.add(new QItem(p.row + 1, p.col, p.dist + 1)); visited[p.row + 1][p.col] = true; } // moving left if (isValid(p.row, p.col - 1, grid, visited)) { queue.add(new QItem(p.row, p.col - 1, p.dist + 1)); visited[p.row][p.col - 1] = true; } // moving right if (isValid(p.row, p.col + 1, grid, visited)) { queue.add(new QItem(p.row, p.col + 1, p.dist + 1)); visited[p.row][p.col + 1] = true; } } return -1; } // checking where it's valid or not private static boolean isValid(int x, int y, char[][] grid, boolean[][] visited) { if (x >= 0 && y >= 0 && x < grid.length && y < grid[0].length && grid[x][y] != '0' && visited[x][y] == false) { return true; } return false; } // Driver code public static void main(String[] args) { char[][] grid = { { '0', '*', '0', 's' }, { '*', '0', '*', '*' }, { '0', '*', '*', '*' }, { 'd', '*', '*', '*' } }; System.out.println(minDistance(grid)); }}// This code is contributed by abhikelge21. |
Python3
# Python3 Code implementation for above problem# QItem for current location and distance# from source locationclass QItem: def __init__(self, row, col, dist): self.row = row self.col = col self.dist = dist def __repr__(self): return f"QItem({self.row}, {self.col}, {self.dist})"def minDistance(grid): source = QItem(0, 0, 0) # Finding the source to start from for row in range(len(grid)): for col in range(len(grid[row])): if grid[row][col] == 's': source.row = row source.col = col break # To maintain location visit status visited = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))] # applying BFS on matrix cells starting from source queue = [] queue.append(source) visited[source.row][source.col] = True while len(queue) != 0: source = queue.pop(0) # Destination found; if (grid[source.row][source.col] == 'd'): return source.dist # moving up if isValid(source.row - 1, source.col, grid, visited): queue.append(QItem(source.row - 1, source.col, source.dist + 1)) visited[source.row - 1][source.col] = True # moving down if isValid(source.row + 1, source.col, grid, visited): queue.append(QItem(source.row + 1, source.col, source.dist + 1)) visited[source.row + 1][source.col] = True # moving left if isValid(source.row, source.col - 1, grid, visited): queue.append(QItem(source.row, source.col - 1, source.dist + 1)) visited[source.row][source.col - 1] = True # moving right if isValid(source.row, source.col + 1, grid, visited): queue.append(QItem(source.row, source.col + 1, source.dist + 1)) visited[source.row][source.col + 1] = True return -1# checking where move is valid or notdef isValid(x, y, grid, visited): if ((x >= 0 and y >= 0) and (x < len(grid) and y < len(grid[0])) and (grid[x][y] != '0') and (visited[x][y] == False)): return True return False# Driver codeif __name__ == '__main__': grid = [['0', '*', '0', 's'], ['*', '0', '*', '*'], ['0', '*', '*', '*'], ['d', '*', '*', '*']] print(minDistance(grid)) # This code is contributed by sajalmittaldei. |
C#
using System;using System.Collections.Generic;// C# Code implementation for above problem// QItem for current location and distance// from source locationpublic class QItem { public int row; public int col; public int dist; public QItem(int x, int y, int w) { this.row = x; this.col = y; this.dist = w; }}public static class GFG { static int N = 4; static int M = 4; public static int minDistance(char[, ] grid) { QItem source = new QItem(0, 0, 0); // To keep track of visited QItems. Marking // blocked cells as visited. bool[, ] visited = new bool[N, M]; ; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (grid[i, j] == '0') { visited[i, j] = true; } else { visited[i, j] = false; } // Finding source if (grid[i, j] == 's') { source.row = i; source.col = j; } } } // applying BFS on matrix cells starting from source Queue<QItem> q = new Queue<QItem>(); q.Enqueue(source); visited[source.row, source.col] = true; while (q.Count > 0) { QItem p = q.Peek(); q.Dequeue(); // Destination found; if (grid[p.row, p.col] == 'd') { return p.dist; } // moving up if (p.row - 1 >= 0 && visited[p.row - 1, p.col] == false) { q.Enqueue(new QItem(p.row - 1, p.col, p.dist + 1)); visited[p.row - 1, p.col] = true; } // moving down if (p.row + 1 < N && visited[p.row + 1, p.col] == false) { q.Enqueue(new QItem(p.row + 1, p.col, p.dist + 1)); visited[p.row + 1, p.col] = true; } // moving left if (p.col - 1 >= 0 && visited[p.row, p.col - 1] == false) { q.Enqueue(new QItem(p.row, p.col - 1, p.dist + 1)); visited[p.row, p.col - 1] = true; } // moving right if (p.col + 1 < M && visited[p.row, p.col + 1] == false) { q.Enqueue(new QItem(p.row, p.col + 1, p.dist + 1)); visited[p.row, p.col + 1] = true; } } return -1; } // Driver code public static void Main() { char[, ] grid = { { '0', '*', '0', 's' }, { '*', '0', '*', '*' }, { '0', '*', '*', '*' }, { 'd', '*', '*', '*' } }; Console.Write(minDistance(grid)); }}// This code is contributed by Aarti_Rathi |
Javascript
<script>// Javascript Code implementation for above problemvar N = 4;var M = 4;// QItem for current location and distance// from source locationclass QItem { constructor(x, y, w) { this.row = x; this.col = y; this.dist = w; }};function minDistance(grid){ var source = new QItem(0, 0, 0); // To keep track of visited QItems. Marking // blocked cells as visited. var visited = Array.from(Array(N), ()=>Array(M).fill(0)); for (var i = 0; i < N; i++) { for (var j = 0; j < M; j++) { if (grid[i][j] == '0') visited[i][j] = true; else visited[i][j] = false; // Finding source if (grid[i][j] == 's') { source.row = i; source.col = j; } } } // applying BFS on matrix cells starting from source var q = []; q.push(source); visited[source.row][source.col] = true; while (q.length!=0) { var p = q[0]; q.shift(); // Destination found; if (grid[p.row][p.col] == 'd') return p.dist; // moving up if (p.row - 1 >= 0 && visited[p.row - 1][p.col] == false) { q.push(new QItem(p.row - 1, p.col, p.dist + 1)); visited[p.row - 1][p.col] = true; } // moving down if (p.row + 1 < N && visited[p.row + 1][p.col] == false) { q.push(new QItem(p.row + 1, p.col, p.dist + 1)); visited[p.row + 1][p.col] = true; } // moving left if (p.col - 1 >= 0 && visited[p.row][p.col - 1] == false) { q.push(new QItem(p.row, p.col - 1, p.dist + 1)); visited[p.row][p.col - 1] = true; } // moving right if (p.col + 1 < M && visited[p.row][p.col + 1] == false) { q.push(new QItem(p.row, p.col + 1, p.dist + 1)); visited[p.row][p.col + 1] = true; } } return -1;}// Driver codevar grid = [ [ '0', '*', '0', 's' ], [ '*', '0', '*', '*' ], [ '0', '*', '*', '*' ], [ 'd', '*', '*', '*' ] ];document.write(minDistance(grid));// This code is contributed by rrrtnx.</script> |
Output
6
Time Complexity: O(N x M)
Auxiliary Space: O(N x M)
This article is contributed by Aarti_Rathi and Prashant Singh. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
