Given a matrix arr[][] of dimensions N * M, having elements 0, 1, and 2. There is only one cell with value 1 present in the matrix. The task is to check if it is possible for 1 to reach the bottom right corner before any cell valued 2 or not using the following operations:
- 2 can replicate itself 1 unit in all four directions in 1 unit of time.
- 1 can only move in one direction among all four directions if the element at that position is 0.
Print “Yes” if a cell with value 1 will reach the bottom right corner in less than or equal amount of time than any cell with value 2. Otherwise, print “1″.
Examples:
Input: N = 3, M = 3, arr[][] = {{0, 2, 0}, {0, 1, 0}, {0, 0, 0}}
Output: Yes
Explanation:
1 can move to the bottom right corner in 2 moves and 2 can move to bottom right corner in 3 moves.
Since, cell with value 1 reaches first than the cell with value 2. Therefore, print Yes.Input: N = 3, M = 3, arr[][] = {{0, 2, 0}, {0, 1, 0}, {0, 2, 0}}
Output: No
Explanation:
1 can move to the bottom right corner in 2 moves and 2 in the last row of the cell can move to bottom right corner in 1 moves.
Since, cell with value 2 reaches first than the cell with value 1. Therefore, print No.
Approach: The idea is to use a Multi-Source BFS. To perform multi-source BFS Traversal, add all the positions of 1 and 2s present in the matrix, in a Deque in the specified order. Perform the BFS on that dequeue by popping out the added positions and adding the adjacent positions that have not yet been visited. Follow the steps below to solve the problem:
- Create a dequeue for multi-source BFS.
- Firstly, add the position having 1 to the front and then add positions having 2 at the back. This is because if 1 and 2 reach the bottom right at the same time then 1 is considered over 2.
- Pop the elements from the front of the dequeue until the dequeue is empty and do the following:
- If the popped position is already visited, proceed to the next position.
- If the position is not visited, check if it’s a bottom-right position or not as well as check if the element in it is 1 or not. If found to be true, then print Yes.
- Otherwise, for all the four directions, insert the current positions in the dequeue.
- Once the above operations are exhausted, if the cell valued 1 is not found to have reached the bottom-right position, then print No.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if cell with// value 1 doesn't reaches the bottom// right cell or notbool reachesBottom(vector<vector<int> >& a){ // Number of rows and columns int n = a.size(); int m = a[0].size(); // Initialise the deque deque<vector<int> > q; // Traverse the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // Push 1 to front of queue if (a[i][j] == 1) { q.push_front({ i, j, 1 }); } // Push 2 to back of queue else if (a[i][j] == 2) { q.push_back({ i, j, 2 }); } a[i][j] = 0; } } // Store all the possible direction // of the current cell int dx[] = { -1, 0, 1, 0 }; int dy[] = { 0, 1, 0, -1 }; // Run multi-source BFS while (!q.empty()) { // Get the front element auto front = q.front(); // Pop the front element q.pop_front(); int i = front[0], j = front[1]; int t = front[2]; if (a[i][j]) continue; a[i][j] = 1; // If 1 reached corner first if (t == 1 and (i == n - 1 && j == m - 1)) { return true; } for (int d = 0; d < 4; d++) { int ni = i + dx[d]; int nj = j + dy[d]; // Insert new point in queue if (ni >= 0 and ni < n and nj >= 0 and nj < m) { q.push_back({ ni, nj, t }); } } } // If 1 can't reach the bottom // right then return false return false;}// Driver Codeint main(){ // Given matrix vector<vector<int> > matrix{ { 0, 2, 0 }, { 0, 1, 0 }, { 0, 2, 0 } }; // Function Call if (reachesBottom(matrix)) { cout << "YES"; } else { cout << "NO"; } return 0;} |
Java
// Java program for the above approachimport java.util.*;import java.lang.*;class GFG{// Function to check if cell with// value 1 doesn't reaches the bottom// right cell or notstatic boolean reachesBottom(int[][] a){ // Number of rows and columns int n = a.length; int m = a[0].length; // Initialise the deque Deque<int[]> q = new LinkedList<>(); // Traverse the matrix for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { // Push 1 to front of queue if (a[i][j] == 1) { q.addFirst(new int[]{ i, j, 1 }); } // Push 2 to back of queue else if (a[i][j] == 2) { q.addLast(new int[]{ i, j, 2 }); } a[i][j] = 0; } } // Store all the possible direction // of the current cell int dx[] = { -1, 0, 1, 0 }; int dy[] = { 0, 1, 0, -1 }; // Run multi-source BFS while (!q.isEmpty()) { // Get the front element int[] front = q.peekFirst(); // Pop the front element q.removeFirst(); int i = front[0], j = front[1]; int t = front[2]; if (a[i][j] == 1) continue; a[i][j] = 1; // If 1 reached corner first if (t == 1 && (i == n - 1 && j == m - 1)) { return true; } for(int d = 0; d < 4; d++) { int ni = i + dx[d]; int nj = j + dy[d]; // Insert new point in queue if (ni >= 0 && ni < n && nj >= 0 && nj < m) { q.addLast(new int[]{ ni, nj, t }); } } } // If 1 can't reach the bottom // right then return false return false;}// Driver Codepublic static void main (String[] args){ // Given matrix int[][] matrix = { { 0, 2, 0 }, { 0, 1, 0 }, { 0, 2, 0 } }; // Function call if (reachesBottom(matrix)) { System.out.print("YES"); } else { System.out.print("NO"); }}}// This code is contributed by offbeat |
Python3
# Python3 program for the above approachfrom collections import deque# Function to check if cell with# value 1 doesn't reaches the bottom# right cell or notdef reachesBottom(a): # Number of rows and columns n = len(a) m = len(a[0]) # Initialise the deque q = deque() # Traverse the matrix for i in range(n): for j in range(m): # Push 1 to front of queue if (a[i][j] == 1): q.appendleft([i, j, 1]) # Push 2 to back of queue elif (a[i][j] == 2): q.append([i, j, 2]) a[i][j] = 0 # Store all the possible direction # of the current cell dx = [ -1, 0, 1, 0 ] dy = [ 0, 1, 0, -1 ] # Run multi-source BFS while (len(q) > 0): # Get the front element front = q.popleft() i = front[0] j = front[1] t = front[2] if (a[i][j]): continue a[i][j] = 1 # If 1 reached corner first if (t == 1 and (i == n - 1 and j == m - 1)): return True for d in range(4): ni = i + dx[d] nj = j + dy[d] # Insert new point queue if (ni >= 0 and ni < n and nj >= 0 and nj < m): q.append([ni, nj, t]) # If 1 can't reach the bottom # right then return false return False# Driver Codeif __name__ == '__main__': # Given matrix matrix = [ [ 0, 2, 0 ], [ 0, 1, 0 ], [ 0, 2, 0 ] ] # Function call if (reachesBottom(matrix)): print("YES") else: print("NO")# This code is contributed by mohit kumar 29 |
C#
// C# program for // the above approachusing System;using System.Collections.Generic;class GFG{// Function to check if cell with// value 1 doesn't reaches the bottom// right cell or notstatic bool reachesBottom(int [,]a, int n, int m){ // Initialise the deque Queue<int[]> q = new Queue<int[]>(); // Traverse the matrix for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { // Push 1 to front of queue if (a[i, j] == 1) { q.Enqueue(new int[]{i, j, 1}); } // Push 2 to back of queue else if (a[i, j] == 2) { q.Enqueue(new int[]{i, j, 2}); } a[i, j] = 0; } } // Store all the possible direction // of the current cell int []dx = {-1, 0, 1, 0}; int []dy = {0, 1, 0, -1}; // Run multi-source BFS while (q.Count != 0) { // Get the front element int[] front = q.Peek(); // Pop the front element q.Dequeue(); int i = front[0], j = front[1]; int t = front[2]; if (a[i, j] == 1) continue; a[i, j] = 1; // If 1 reached corner first if (t == 1 && (i == n - 1 && j == m - 1)) { return true; } for(int d = 0; d < 4; d++) { int ni = i + dx[d]; int nj = j + dy[d]; // Insert new point in queue if (ni >= 0 && ni < n && nj >= 0 && nj < m) { q.Enqueue(new int[]{ni, nj, t}); } } } // If 1 can't reach the bottom // right then return false return false;}// Driver Codepublic static void Main(String[] args){ // Given matrix int[,] matrix = {{0, 2, 0}, {0, 1, 0}, {0, 2, 0}}; // Function call if (reachesBottom(matrix, 3, 3)) { Console.Write("YES"); } else { Console.Write("NO"); }}}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript program for the above approach// Function to check if cell with// value 1 doesn't reaches the bottom// right cell or notfunction reachesBottom(a){ // Number of rows and columns var n = a.length; var m = a[0].length; // Initialise the deque var q = []; // Traverse the matrix for (var i = 0; i < n; i++) { for (var j = 0; j < m; j++) { // Push 1 to front of queue if (a[i][j] == 1) { q.slice(0,0,[i, j, 1]); } // Push 2 to back of queue else if (a[i][j] == 2) { q.push([i, j, 2 ]); } a[i][j] = 0; } } // Store all the possible direction // of the current cell var dx = [-1, 0, 1, 0 ]; var dy = [ 0, 1, 0, -1 ]; // Run multi-source BFS while (!q.length) { // Get the front element var front = q[0]; // Pop the front element q.shift(); var i = front[0], j = front[1]; var t = front[2]; if (a[i][j]) continue; a[i][j] = 1; // If 1 reached corner first if (t == 1 && (i == n - 1 && j == m - 1)) { return true; } for (var d = 0; d < 4; d++) { var ni = i + dx[d]; var nj = j + dy[d]; // Insert new point in queue if (ni >= 0 && ni < n && nj >= 0 && nj < m) { q.push([ ni, nj, t ]); } } } // If 1 can't reach the bottom // right then return false return false;}// Driver Code// Given matrixvar matrix = [[ 0, 2, 0 ], [ 0, 1, 0 ], [0, 2, 0 ]];// Function Callif (reachesBottom(matrix)) { document.write( "YES");}else { document.write( "NO");}</script> |
NO
Time Complexity: O(N*M), The time complexity is O(N*M), where N is the number of rows and M is the number of columns in the given matrix. This is because the program traverses every cell of the matrix once to initialize the deque and again during the BFS traversal. In the worst case, all cells of the matrix may be traversed, resulting in O(N*M) time complexity.
Auxiliary Space: O(N*M), The space complexity of the program is also O(N*M). This is because the program initializes a deque to store all the possible directions of the current cell. In the worst case, the deque may store all the cells of the matrix, resulting in O(N*M) space complexity. Additionally, the program also initializes a 2D vector to represent the matrix, which also takes O(N*M) space. Therefore, the overall space complexity of the program is O(N*M).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
