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 2Input: 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 directionsint 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 matrixvoid 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 Codeint 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 approachimport 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 directionsstatic 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 matrixstatic 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 Codepublic 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 approachmat = [[0 for x in range(1001)] for y in range(1001)]# Stores the accessible directionsdx = [ 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 matrixdef 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 Coder = 5c = 5x = 1y = 1t = xl = ymat[x][y] = 0FindMinimumDistance()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 approachusing 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 directionsstatic 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 matrixstatic 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 Codepublic 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:
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
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
