Shortest distance between two cells in a matrix or grid

Last Updated : 22 Jun, 2022

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 location
class 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 code
int 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 problem
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
// QItem for current location and distance
// from source location
class 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 location
class 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 not
def 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 code
if __name__ == '__main__':
    grid = [['0', '*', '0', 's'],
            ['*', '0', '*', '*'],
            ['0', '*', '*', '*'],
            ['d', '*', '*', '*']]
 
    print(minDistance(grid))
 
    # This code is contributed by sajalmittaldei.

C#

Javascript

<script>
 
// Javascript Code implementation for above problem
var N = 4;
var M = 4;
 
// QItem for current location and distance
// from source location
class 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 code
var grid = [ [ '0', '*', '0', 's' ],
                    [ '*', '0', '*', '*' ],
                    [ '0', '*', '*', '*' ],
                    [ 'd', '*', '*', '*' ] ];
document.write(minDistance(grid));
 
// This code is contributed by rrrtnx.
 
</script>

Output

Time Complexity: O(N x M)
Auxiliary Space: O(N x M)

Suggest improvement

Maximum cost path from source node to destination node via at most K intermediate nodes

Snake and Ladder Problem

Share your thoughts in the comments

Queue implementation in different languages

Some question related to Queue implementation

Easy problems on Queue

Intermediate problems on Queue

Hard problems on Queue