Given a binary matrix grid[][] of size M*N where ‘0‘ represents a blocked cell and ‘1’ represents a normal cell and a source (sx, sy) and destination (dx, dy). The task is to check if the destination is reachable from the source by moving at most K units of distance in a single step.
Examples:
Input: M = 4, N = 4, grid[][] = [[1, 1, 1, 1], [1, 0, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]], sx = 0, sy = 0, dx = 3, dy = 3, K = 3
Output: True
Explanation: In this test case, the distance from the source to the destination is 3, which is less than or equal to K. Therefore, the destination is reachable.Input: M = 4, N = 4, grid[][] = [[1, 1, 1, 1], [1, 0, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]], sx = 0, sy = 0, dx = 3, dy = 3, K = 2
Output: False
Explanation: In this test case, the distance from the source to the destination is 3, which is greater than K. Therefore, the destination is not reachable.
Approach: The above problem can be solved using the below idea:
Adding the source to the queue. Explore all the points that can be reached from the top point of the queue and add them to the queue along with the distance covered. Keep checking whether a point has been visited or not. If the destination point is reached return true, otherwise false.
Follow the below steps to implement the idea:
- Initialize an empty queue to store the cells we need to explore, and a 2D array to store the distance from the source for each cell.
- Add the source cell to the queue and set its distance to 0.
- While there are cells in the queue to explore:
- Get the next cell to explore from the queue.
- If the cell is the destination, return true.
- Otherwise, explore the cells that can be reached in one step from the current cell.
- For each valid and unexplored cell:
- Add the cell to the queue and update its distance from the source.
- If the distance from the source is greater than K, stop exploring this cell.
- If we have explored all the cells and have not found the destination, return false.
Below is the implementation of the above approach.
C++
#include<bits/stdc++.h>using namespace std;// Function to check whether point lies within// the boundarybool isValid(vector<vector<int>>& grid, int x, int y, int m, int n){ // Check if the cell is within the grid // boundaries and not blocked return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1;}// Function to check whether it is possible to// reach destination from source.int isDestinationReachable(vector<vector<int>>& grid, int sx, int sy, int dx, int dy, int k) { int m = grid.size(); int n = grid[0].size(); // Create a queue to store the cells // we need to explore queue<pair<int,int>>Queue;; // Create a 2D array to store the distance // from the source for each cell vector<vector<int>> distances(m,vector<int>(n,-1)); // Add the source cell to the queue and // set its distance to 0 Queue.push({sx, sy}); distances[sx][sy] = 0; // Directions to move in the grid int dxi[] = {1, 0, -1, 0, -1, 1}; int dyj[] = {0, 1, 0, -1, -1, 1}; // While there are cells in the queue to explore while (!Queue.empty()) { // Get the next cell to explore auto p = Queue.front(); Queue.pop(); int x=p.first; int y=p.second; // If we have reached the destination, // return true if (x == dx && y == dy) { return true; } // Otherwise, explore the cells that can be // reached in one step for (int i = 0; i < 4; i++) { int new_x = x + dxi[i]; int new_y = y + dyj[i]; // If the new cell is valid and has // not been explored yet if (isValid(grid, new_x, new_y, m, n) && distances[new_x][new_y] == -1) { // Add the new cell to the queue and // update its distance from the source Queue.push({new_x, new_y}); distances[new_x][new_y] = distances[x][y] + 1; // If the distance from the source is // greater than k, stop exploring this cell if (distances[new_x][new_y] > k) { return false; } } } } // If we have explored all the cells and not // found the destination, return false return false;}// Driver codeint main(){ vector<vector<int>> grid = {{1, 0, 1, 1},{1, 0, 1, 1},{1, 1, 1, 1},{1, 1, 1, 1}}; int sx = 0; int sy = 0; int dx = 3; int dy = 3; int k = 3; // Function call if(isDestinationReachable(grid, sx, sy, dx, dy, k)) cout<<"True"; else cout<<"False"; return 0;}// This code is contributed by ratiagrawal. |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { // Directions to move in the grid static int[] dxi = { 1, 0, -1, 0, -1, 1 }; static int[] dyj = { 0, 1, 0, -1, -1, 1 }; // Function to check whether point lies within the // boundary static boolean isValid(int[][] grid, int x, int y, int m, int n) { // Check if the cell is within the grid boundaries // and not blocked return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1; } // Function to check whether it is possible to reach // destination from source. static boolean isDestinationReachable(int[][] grid, int sx, int sy, int dx, int dy, int k) { int m = grid.length; int n = grid[0].length; // Create a queue to store the cells we need to // explore Queue<int[]> Queue = new LinkedList<>(); // Create a 2D array to store the distance from the // source for each cell int[][] distances = new int[m][n]; for (int i = 0; i < m; i++) { Arrays.fill(distances[i], -1); } // Add the source cell to the queue and set its // distance to 0 Queue.add(new int[] { sx, sy }); distances[sx][sy] = 0; // While there are cells in the queue to explore while (!Queue.isEmpty()) { // Get the next cell to explore int[] p = Queue.remove(); int x = p[0]; int y = p[1]; // If we have reached the destination, return // true if (x == dx && y == dy) { return true; } // Otherwise, explore the cells that can be // reached in one step for (int i = 0; i < 4; i++) { int new_x = x + dxi[i]; int new_y = y + dyj[i]; // If the new cell is valid and has not been // explored yet if (isValid(grid, new_x, new_y, m, n) && distances[new_x][new_y] == -1) { // Add the new cell to the queue and // update its distance from the source Queue.add(new int[] { new_x, new_y }); distances[new_x][new_y] = distances[x][y] + 1; // If the distance from the source is // greater than k, stop exploring this // cell if (distances[new_x][new_y] > k) { return false; } } } } // If we have explored all the cells and not found // the destination, return false return false; } public static void main(String[] args) { int[][] grid = { { 1, 0, 1, 1 }, { 1, 0, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 1 } }; int sx = 0; int sy = 0; int dx = 3; int dy = 3; int k = 3; // Function call if (isDestinationReachable(grid, sx, sy, dx, dy, k)) { System.out.println("True"); } else { System.out.println("False"); } }}// This code is contributed by karthik. |
Python3
# Python code to implement the approach# Function to check whether it is possible to# reach destination from source.def isDestinationReachable(grid, sx, sy, dx, dy, k): m = len(grid) n = len(grid[0]) # Create a queue to store the cells # we need to explore queue = [] # Create a 2D array to store the distance # from the source for each cell distances = [[-1 for j in range(n)] for i in range(m)] # Add the source cell to the queue and # set its distance to 0 queue.append((sx, sy)) distances[sx][sy] = 0 # Directions to move in the grid dx = [1, 0, -1, 0, -1, 1] dy = [0, 1, 0, -1, -1, 1] # While there are cells in the queue to explore while queue: # Get the next cell to explore x, y = queue.pop(0) # If we have reached the destination, # return true if x == dx and y == dy: return True # Otherwise, explore the cells that can be # reached in one step for i in range(4): new_x = x + dx[i] new_y = y + dy[i] # If the new cell is valid and has # not been explored yet if isValid(grid, new_x, new_y, m, n) \ and distances[new_x][new_y] == -1: # Add the new cell to the queue and # update its distance from the source queue.append((new_x, new_y)) distances[new_x][new_y] = distances[x][y] + 1 # If the distance from the source is # greater than k, stop exploring this cell if distances[new_x][new_y] > k: break # If we have explored all the cells and not # found the destination, return false return False# Function to check whether point lies within# the boundarydef isValid(grid, x, y, m, n): # Check if the cell is within the grid # boundaries and not blocked return x >= 0 and x < m and y >= 0 and y < n and grid[x][y] == 1# Driver codeif __name__ == '__main__': # Input grid = [[1, 0, 1, 1], [1, 0, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1] ] sx = 0 sy = 0 dx = 3 dy = 3 K = 3 # Function call print(isDestinationReachable(grid, sx, sy, dx, dy, K)) |
C#
using System;using System.Collections.Generic;public class GFG{ // Directions to move in the grid static int[] dxi = { 1, 0, -1, 0, -1, 1 }; static int[] dyj = { 0, 1, 0, -1, -1, 1 }; // Function to check whether point lies within the // boundary static bool IsValid(int[,] grid, int x, int y, int m, int n) { // Check if the cell is within the grid boundaries // and not blocked return x >= 0 && x < m && y >= 0 && y < n && grid[x, y] == 1; } // Function to check whether it is possible to reach // destination from source. static bool IsDestinationReachable(int[,] grid, int sx, int sy, int dx, int dy, int k) { int m = grid.GetLength(0); int n = grid.GetLength(1); // Create a queue to store the cells we need to // explore Queue<int[]> Queue = new Queue<int[]>(); // Create a 2D array to store the distance from the // source for each cell int[,] distances = new int[m, n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { distances[i, j] = -1; } } // Add the source cell to the queue and set its // distance to 0 Queue.Enqueue(new int[] { sx, sy }); distances[sx, sy] = 0; // While there are cells in the queue to explore while (Queue.Count > 0) { // Get the next cell to explore int[] p = Queue.Dequeue(); int x = p[0]; int y = p[1]; // If we have reached the destination, return // true if (x == dx && y == dy) { return true; } // Otherwise, explore the cells that can be // reached in one step for (int i = 0; i < 4; i++) { int new_x = x + dxi[i]; int new_y = y + dyj[i]; // If the new cell is valid and has not been // explored yet if (IsValid(grid, new_x, new_y, m, n) && distances[new_x, new_y] == -1) { // Add the new cell to the queue and // update its distance from the source Queue.Enqueue(new int[] { new_x, new_y }); distances[new_x, new_y] = distances[x, y] + 1; // If the distance from the source is // greater than k, stop exploring this // cell if (distances[new_x, new_y] > k) { return false; } } } } // If we have explored all the cells and not found // the destination, return false return false; } public static void Main (string[] args) { int[,] grid = new int[,] { { 1, 0, 1, 1 }, { 1, 0, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 1 } }; int sx = 0; int sy = 0; int dx = 3; int dy = 3; int k = 3; // Function call if (IsDestinationReachable(grid, sx, sy, dx, dy, k)) { Console.WriteLine("True"); } else { Console.WriteLine("False"); } }} |
Javascript
// Function to check whether it is possible to// reach destination from source.function isDestinationReachable(grid, sx, sy, dx, dy, k) { let m = grid.length; let n = grid[0].length; // Create a queue to store the cells // we need to explore let queue = []; // Create a 2D array to store the distance // from the source for each cell let distances = Array(m) .fill(0) .map(() => Array(n).fill(-1)); // Add the source cell to the queue and // set its distance to 0 queue.push([sx, sy]); distances[sx][sy] = 0; // Directions to move in the grid let dxi = [1, 0, -1, 0, -1, 1]; let dyj = [0, 1, 0, -1, -1, 1]; // While there are cells in the queue to explore while (queue.length) { // Get the next cell to explore let [x, y] = queue.shift(); // If we have reached the destination, // return true if (x === dx && y === dy) { return true; } // Otherwise, explore the cells that can be // reached in one step for (let i = 0; i < 4; i++) { let new_x = x + dxi[i]; let new_y = y + dyj[i]; // If the new cell is valid and has // not been explored yet if (isValid(grid, new_x, new_y, m, n) && distances[new_x][new_y] == -1) { // Add the new cell to the queue and // update its distance from the source queue.push([new_x, new_y]); distances[new_x][new_y] = distances[x][y] + 1; // If the distance from the source is // greater than k, stop exploring this cell if (distances[new_x][new_y] > k) { return false; } } } } // If we have explored all the cells and not // found the destination, return false return false;}// Function to check whether point lies within// the boundaryfunction isValid(grid, x, y, m, n) { // Check if the cell is within the grid // boundaries and not blocked return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1;}// Driver codelet grid = [ [1, 0, 1, 1], [1, 0, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1],];let sx = 0;let sy = 0;let dx = 3;let dy = 3;let k = 3;// Function callconsole.log(isDestinationReachable(grid, sx, sy, dx, dy, k));// This code is contributed by lokeshpotta20. |
Output
False
Time Complexity: O(M * N)
Auxiliary Space: O(M * N)
Related Articles:
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!
