Minimum Distance from a given Cell to all other Cells of a Matrix

0 0 7 minutes read

Given two integers R and C, denoting the number of rows and columns in a matrix, and two integers X and Y, the task is to find the minimum distance from the given cell to all other cells of the matrix.

Examples:

Input: R = 5, C = 5, X = 2, Y = 2
Output:
2 2 2 2 2
2 1 1 1 2
2 1 0 1 2
2 1 1 1 2
2 2 2 2 2

Input: R = 5, C = 5, X = 1, Y = 1
Output:
1 1 1 2 3
1 0 1 2 3
1 1 1 2 3
2 2 2 2 3
3 3 3 3 3

Approach:
Follow the steps below to solve the problem:

Assign the distance of the initial cells as 0.
Initialize a Queue and insert the pair {X, Y} into the Queue.
Iterate until the Queue is not empty, and for every unvisited cell, assign the current distance and insert the index {i, j} into the Queue using the BFS technique.
Print the distance of each cell at the end.

Below is the implementation of the above approach:

C++

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
int mat[1001][1001];
int r, c, x, y;
 
// Stores the accessible directions
int dx[] = { 0, -1, -1, -1, 0, 1, 1, 1 };
int dy[] = { 1, 1, 0, -1, -1, -1, 0, 1 };
 
// Function to find the minimum distance from a
// given cell to all other cells in the matrix
void FindMinimumDistance()
{
    // Stores the accessible cells
    // from current cell
    queue<pair<int, int> > q;
 
    // Insert pair (x, y)
    q.push({ x, y });
    mat[x][y] = 0;
 
    // Iterate until queue is empty
    while (!q.empty()) {
 
        // Extract the pair
        x = q.front().first;
        y = q.front().second;
 
        // Pop them
        q.pop();
 
        for (int i = 0; i < 8; i++) {
            int a = x + dx[i];
            int b = y + dy[i];
 
            // Checking boundary condition
            if (a < 0 || a >= r || b >= c || b < 0)
                continue;
 
            // If the cell is not visited
            if (mat[a][b] == 0) {
 
                // Assign the minimum distance
                mat[a][b] = mat[x][y] + 1;
 
                // Insert the traversed neighbour
                // into the queue
                q.push({ a, b });
            }
        }
    }
}
 
// Driver Code
int main()
{
    r = 5, c = 5, x = 1, y = 1;
 
    int t = x;
    int l = y;
    mat[x][y] = 0;
 
    FindMinimumDistance();
 
    mat[t][l] = 0;
 
    // Print the required distances
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cout << mat[i][j] << " ";
        }
        cout << endl;
    }
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
     
static class pair
{ 
    int first, second; 
    public pair(int first, int second) 
    { 
        this.first = first; 
        this.second = second; 
    } 
} 
 
static int [][]mat = new int[1001][1001];
static int r, c, x, y;
 
// Stores the accessible directions
static int dx[] = { 0, -1, -1, -1, 0, 1, 1, 1 };
static int dy[] = { 1, 1, 0, -1, -1, -1, 0, 1 };
 
// Function to find the minimum distance from a
// given cell to all other cells in the matrix
static void FindMinimumDistance()
{
     
    // Stores the accessible cells
    // from current cell
    Queue<pair> q = new LinkedList<>();
 
    // Insert pair (x, y)
    q.add(new pair(x, y));
    mat[x][y] = 0;
 
    // Iterate until queue is empty
    while (!q.isEmpty())
    {
         
        // Extract the pair
        x = q.peek().first;
        y = q.peek().second;
 
        // Pop them
        q.remove();
 
        for(int i = 0; i < 8; i++)
        {
            int a = x + dx[i];
            int b = y + dy[i];
 
            // Checking boundary condition
            if (a < 0 || a >= r ||
               b >= c || b < 0)
                continue;
 
            // If the cell is not visited
            if (mat[a][b] == 0) 
            {
                 
                // Assign the minimum distance
                mat[a][b] = mat[x][y] + 1;
 
                // Insert the traversed neighbour
                // into the queue
                q.add(new pair(a, b));
            }
        }
    }
}
 
// Driver Code
public static void main(String[] args)
{
    r = 5; c = 5; x = 1; y = 1;
 
    int t = x;
    int l = y;
    mat[x][y] = 0;
 
    FindMinimumDistance();
 
    mat[t][l] = 0;
 
    // Print the required distances
    for(int i = 0; i < r; i++)
    {
        for(int j = 0; j < c; j++)
        {
            System.out.print(mat[i][j] + " ");
        }
        System.out.println();
    }
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program to implement
# the above approach
mat = [[0 for x in range(1001)] 
          for y in range(1001)]
 
# Stores the accessible directions
dx = [ 0, -1, -1, -1, 0, 1, 1, 1 ]
dy = [ 1, 1, 0, -1, -1, -1, 0, 1 ]
 
# Function to find the minimum distance
# from a given cell to all other cells
# in the matrix
def FindMinimumDistance():
     
    global x, y, r, c
 
    # Stores the accessible cells
    # from current cell
    q = []
 
    # Insert pair (x, y)
    q.append([x, y])
    mat[x][y] = 0
 
    # Iterate until queue is empty
    while(len(q) != 0):
 
        # Extract the pair
        x = q[0][0]
        y = q[0][1]
 
        # Pop them
        q.pop(0)
 
        for i in range(8):
            a = x + dx[i]
            b = y + dy[i]
 
            # Checking boundary condition
            if(a < 0 or a >= r or
              b >= c or b < 0):
                continue
 
            # If the cell is not visited
            if(mat[a][b] == 0):
 
                # Assign the minimum distance
                mat[a][b] = mat[x][y] + 1
 
                # Insert the traversed neighbour
                # into the queue
                q.append([a, b])
 
# Driver Code
r = 5
c = 5
x = 1
y = 1
t = x
l = y
 
mat[x][y] = 0
 
FindMinimumDistance()
mat[t][l] = 0
 
# Print the required distances 
for i in range(r):
    for j in range(c):
        print(mat[i][j], end = " ")
         
    print()
 
# This code is contributed by Shivam Singh

C#

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
class GFG{
     
class pair
{ 
    public int first, second; 
    public pair(int first, int second) 
    { 
        this.first = first; 
        this.second = second; 
    } 
} 
 
static int [,]mat = new int[1001, 1001];
static int r, c, x, y;
 
// Stores the accessible directions
static int []dx = { 0, -1, -1, -1, 0, 1, 1, 1 };
static int []dy = { 1, 1, 0, -1, -1, -1, 0, 1 };
 
// Function to find the minimum distance from a
// given cell to all other cells in the matrix
static void FindMinimumDistance()
{
     
    // Stores the accessible cells
    // from current cell
    Queue<pair> q = new Queue<pair>();
 
    // Insert pair (x, y)
    q.Enqueue(new pair(x, y));
    mat[x, y] = 0;
 
    // Iterate until queue is empty
    while (q.Count != 0)
    {
         
        // Extract the pair
        x = q.Peek().first;
        y = q.Peek().second;
 
        // Pop them
        q.Dequeue();
 
        for(int i = 0; i < 8; i++)
        {
            int a = x + dx[i];
            int b = y + dy[i];
 
            // Checking boundary condition
            if (a < 0 || a >= r ||
                b >= c || b < 0)
                continue;
 
            // If the cell is not visited
            if (mat[a, b] == 0) 
            {
                 
                // Assign the minimum distance
                mat[a, b] = mat[x, y] + 1;
 
                // Insert the traversed neighbour
                // into the queue
                q.Enqueue(new pair(a, b));
            }
        }
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    r = 5; c = 5; x = 1; y = 1;
 
    int t = x;
    int l = y;
    mat[x, y] = 0;
 
    FindMinimumDistance();
 
    mat[t, l] = 0;
 
    // Print the required distances
    for(int i = 0; i < r; i++)
    {
        for(int j = 0; j < c; j++)
        {
            Console.Write(mat[i, j] + " ");
        }
        Console.WriteLine();
    }
}
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
    // Javascript Program to implement the above approach
     
    let mat = new Array(1001);
    for(let i = 0; i < 1001; i++)
    {
        mat[i] = new Array(1001);
        for(let j = 0; j < 1001; j++)
        {    
            mat[i][j] = 0;
        }
    }
    let r, c, x, y;
 
    // Stores the accessible directions
    let dx = [ 0, -1, -1, -1, 0, 1, 1, 1 ];
    let dy = [ 1, 1, 0, -1, -1, -1, 0, 1 ];
 
    // Function to find the minimum distance from a
    // given cell to all other cells in the matrix
    function FindMinimumDistance()
    {
        // Stores the accessible cells
        // from current cell
        let q = [];
 
        // Insert pair (x, y)
        q.push([ x, y ]);
        mat[x][y] = 0;
 
        // Iterate until queue is empty
        while (q.length > 0) {
 
            // Extract the pair
            x = q[0][0];
            y = q[0][1];
 
            // Pop them
            q.shift();
 
            for (let i = 0; i < 8; i++) {
                let a = x + dx[i];
                let b = y + dy[i];
 
                // Checking boundary condition
                if (a < 0 || a >= r || b >= c || b < 0)
                    continue;
 
                // If the cell is not visited
                if (mat[a][b] == 0) {
 
                    // Assign the minimum distance
                    mat[a][b] = mat[x][y] + 1;
 
                    // Insert the traversed neighbour
                    // into the queue
                    q.push([ a, b ]);
                }
            }
        }
    }
     
    r = 5, c = 5, x = 1, y = 1;
   
    let t = x;
    let l = y;
    mat[x][y] = 0;
   
    FindMinimumDistance();
   
    mat[t][l] = 0;
   
    // Print the required distances
    for (let i = 0; i < r; i++) {
        for (let j = 0; j < c; j++) {
            document.write(mat[i][j] + " ");
        }
        document.write("</br>");
    }
 
</script>

Output:

Time Complexity: O(R * C)
Auxiliary Space: O(R * C)

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 zambiatek!