Count of Reachable cells in Grid within given Left-Right moves
Given a grid of size N X M in which some cells are empty, and some have obstacles, the task is to find how many cells (including the starting cell) are reachable from cell (startRow, startCol) such that number of right moves allowed are R and number of left moves allowed are L.
An obstacle and empty space are marked as 1 and 0 respectively in the grid.
Example:
Input: grid[][] = {{0, 0, 0, 0, 0}, {0, 1, 1, 1, 0}, {0, 0, 0, 1, 1}, {1, 0, 0, 0, 0}}, startRow = 2, startCol = 1, L = 1, R = 2
Output: 10
Explanation: 10 cells are reachable from start (2,1) such that there are no more than 1 left move and no more than 2 right moves.Input: grid[][] = {{0, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}}, startRow = 1, startCol = 1, L = 0, R = 1
Output: 7
Explanation: 7 cells are reachable from start (1,1) such that there are no more than 0 left moves and no more than 1 right move.
Approach: The problem can be solved using the following approach:
The idea is to use 0-1 BFS algorithm to explore the grid from a starting cell. The algorithm maintains a deque of cells to visit, starting with the initial cell. It considers valid moves in all four directions, keeping track of the number of left and right moves allowed. If we move in up or down direction then the new cell is pushed to the front of the deque, else if we move to the left or right then the new cell is pushed to the back of the deque. The algorithm continues to explore cells until the limits on left and right moves are reached or all reachable cells are visited. The count of reachable cells, including the starting cell, is then returned.
Step by step algorithm:
- Enqueue the starting cell(startRow, startCol) and mark it as visited.
- While the queue is not empty, dequeue a cell, count it, and enqueue its unvisited neighboring cells within move constraints.
- If the neighboring cell is in the left or right of the current cell, then push the neighboring cell to the back of the deque else push it to the front of the deque.
- Continue dequeuing and enqueuing until all reachable cells are visited.
- Display the count of reachable cells, including the starting cell.
Below is the implementation of the above approach:
C++14
#include <bits/stdc++.h> using namespace std; // Maximum size for the grid const int MAX_N = 2010; int grid[MAX_N][MAX_N]; int n, m, L, R, startRow, startCol, reachable_cells = 0; // Marking visited cells bool visited[MAX_N][MAX_N]; // Structure to represent a cell in the grid struct Cell { int x, y, left_moves, right_moves; }; // Using deque for 0-1 BFS deque<Cell> dq; // Function to add a cell to the deque based on the // direction void enqueue( int x, int y, int left_moves, int right_moves, bool is_front) { if (x >= 0 && y >= 0 && x < n && y < m && grid[x][y] == 0 && !visited[x][y] && left_moves <= L && right_moves <= R) { visited[x][y] = true ; if (is_front) { dq.push_front( { x, y, left_moves, right_moves }); } else { dq.push_back({ x, y, left_moves, right_moves }); } } } // 0-1 BFS to find reachable cells void bfs() { dq.push_front( { startRow, startCol, 0, 0 }); // Starting cell visited[startRow][startCol] = true ; while (!dq.empty()) { auto current_cell = dq.front(); dq.pop_front(); reachable_cells++; // Explore neighboring cells in all four directions // Left enqueue(current_cell.x - 1, current_cell.y, current_cell.left_moves, current_cell.right_moves, true ); // Right enqueue(current_cell.x + 1, current_cell.y, current_cell.left_moves, current_cell.right_moves, true ); // Upwards enqueue(current_cell.x, current_cell.y - 1, current_cell.left_moves + 1, current_cell.right_moves, false ); // Downwards enqueue(current_cell.x, current_cell.y + 1, current_cell.left_moves, current_cell.right_moves + 1, false ); } } int main() { // Input grid size, starting position, and allowed moves n = 4; m = 5; startRow = 2; startCol = 1; L = 1; R = 2; // Input the grid int input_grid[4][5] = { { 0, 0, 0, 0, 0 }, { 0, 1, 1, 1, 0 }, { 0, 0, 0, 1, 1 }, { 1, 0, 0, 0, 0 } }; // 1 -based indexing for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { grid[i][j] = input_grid[i][j]; } } // Execute 0-1 breadth-first search bfs(); // Output the number of reachable cells cout << reachable_cells << endl; return 0; } |
Java
import java.util.ArrayDeque; import java.util.Deque; // Class to represent a cell in the grid class Cell { int x, y, leftMoves, rightMoves; public Cell( int x, int y, int leftMoves, int rightMoves) { this .x = x; this .y = y; this .leftMoves = leftMoves; this .rightMoves = rightMoves; } } public class GridBFS { // Maximum size for the grid static final int MAX_N = 2010 ; static int [][] grid = new int [MAX_N][MAX_N]; static boolean [][] visited = new boolean [MAX_N][MAX_N]; static int n, m, L, R, startRow, startCol, reachableCells = 0 ; // Using deque for 0-1 BFS static Deque<Cell> dq = new ArrayDeque<>(); // Function to add a cell to the deque based on the direction static void enqueue( int x, int y, int leftMoves, int rightMoves, boolean isFront) { if (x >= 0 && y >= 0 && x < n && y < m && grid[x][y] == 0 && !visited[x][y] && leftMoves <= L && rightMoves <= R) { visited[x][y] = true ; if (isFront) { dq.addFirst( new Cell(x, y, leftMoves, rightMoves)); } else { dq.addLast( new Cell(x, y, leftMoves, rightMoves)); } } } // 0-1 BFS to find reachable cells static void bfs() { dq.addFirst( new Cell(startRow, startCol, 0 , 0 )); // Starting cell visited[startRow][startCol] = true ; while (!dq.isEmpty()) { Cell currentCell = dq.pollFirst(); reachableCells++; // Explore neighboring cells in all four directions // Left enqueue(currentCell.x - 1 , currentCell.y, currentCell.leftMoves, currentCell.rightMoves, true ); // Right enqueue(currentCell.x + 1 , currentCell.y, currentCell.leftMoves, currentCell.rightMoves, true ); // Upwards enqueue(currentCell.x, currentCell.y - 1 , currentCell.leftMoves + 1 , currentCell.rightMoves, false ); // Downwards enqueue(currentCell.x, currentCell.y + 1 , currentCell.leftMoves, currentCell.rightMoves + 1 , false ); } } public static void main(String[] args) { // Input grid size, starting position, and allowed moves n = 4 ; m = 5 ; startRow = 2 ; startCol = 1 ; L = 1 ; R = 2 ; // Input the grid int [][] inputGrid = { { 0 , 0 , 0 , 0 , 0 }, { 0 , 1 , 1 , 1 , 0 }, { 0 , 0 , 0 , 1 , 1 }, { 1 , 0 , 0 , 0 , 0 } }; // Copy input grid for ( int i = 0 ; i < n; i++) { System.arraycopy(inputGrid[i], 0 , grid[i], 0 , m); } // Execute 0-1 breadth-first search bfs(); // Output the number of reachable cells System.out.println(reachableCells); } } // This code is contributed by shivamgupta310570 |
Python3
# Python program for the above approach from collections import deque # Maximum size for the grid MAX_N = 2010 grid = [[ 0 ] * MAX_N for _ in range (MAX_N)] n, m, L, R, startRow, startCol, reachable_cells = 0 , 0 , 0 , 0 , 0 , 0 , 0 # Marking visited cells visited = [[ False ] * MAX_N for _ in range (MAX_N)] # Structure to represent a cell in the grid class Cell: def __init__( self , x, y, left_moves, right_moves): self .x = x self .y = y self .left_moves = left_moves self .right_moves = right_moves # Using deque for 0-1 BFS dq = deque() # Function to add a cell to the deque based on the direction def enqueue(x, y, left_moves, right_moves, is_front): global dq global visited if 0 < = x < n and 0 < = y < m and grid[x][y] = = 0 and not visited[x][y] and left_moves < = L and right_moves < = R: visited[x][y] = True if is_front: dq.appendleft(Cell(x, y, left_moves, right_moves)) else : dq.append(Cell(x, y, left_moves, right_moves)) # 0-1 BFS to find reachable cells def bfs(): global dq global visited global reachable_cells dq.appendleft(Cell(startRow, startCol, 0 , 0 )) # Starting cell visited[startRow][startCol] = True while dq: current_cell = dq.popleft() reachable_cells + = 1 # Explore neighboring cells in all four directions # Left enqueue(current_cell.x - 1 , current_cell.y, current_cell.left_moves, current_cell.right_moves, True ) # Right enqueue(current_cell.x + 1 , current_cell.y, current_cell.left_moves, current_cell.right_moves, True ) # Upwards enqueue(current_cell.x, current_cell.y - 1 , current_cell.left_moves + 1 , current_cell.right_moves, False ) # Downwards enqueue(current_cell.x, current_cell.y + 1 , current_cell.left_moves, current_cell.right_moves + 1 , False ) # Input grid size, starting position, and allowed moves n = 4 m = 5 startRow = 2 startCol = 1 L = 1 R = 2 # Input the grid input_grid = [ [ 0 , 0 , 0 , 0 , 0 ], [ 0 , 1 , 1 , 1 , 0 ], [ 0 , 0 , 0 , 1 , 1 ], [ 1 , 0 , 0 , 0 , 0 ] ] # 1-based indexing for i in range (n): grid[i] = input_grid[i][:] # Execute 0-1 breadth-first search bfs() # Output the number of reachable cells print (reachable_cells) # This code is contributed by Susobhan Akhuli |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class Cell { public int x, y, left_moves, right_moves; } public class GFG { // Maximum size for the grid const int MAX_N = 2010; static int [, ] grid = new int [MAX_N, MAX_N]; static int n, m, L, R, startRow, startCol, reachable_cells = 0; // Marking visited cells static bool [, ] visited = new bool [MAX_N, MAX_N]; // Using deque for 0-1 BFS static LinkedList<Cell> dq = new LinkedList<Cell>(); // Function to add a cell to the deque based on the // direction static void Enqueue( int x, int y, int left_moves, int right_moves, bool is_front) { if (x >= 0 && y >= 0 && x < n && y < m && grid[x, y] == 0 && !visited[x, y] && left_moves <= L && right_moves <= R) { visited[x, y] = true ; if (is_front) { dq.AddFirst( new Cell{ x = x, y = y, left_moves = left_moves, right_moves = right_moves }); } else { dq.AddLast( new Cell{ x = x, y = y, left_moves = left_moves, right_moves = right_moves }); } } } // 0-1 BFS to find reachable cells static void BFS() { dq.AddFirst( new Cell{ x = startRow, y = startCol, left_moves = 0, right_moves = 0 }); // Starting cell visited[startRow, startCol] = true ; while (dq.Count > 0) { var current_cell = dq.First.Value; dq.RemoveFirst(); reachable_cells++; // Explore neighboring cells in all four // directions Left Enqueue(current_cell.x - 1, current_cell.y, current_cell.left_moves, current_cell.right_moves, true ); // Right Enqueue(current_cell.x + 1, current_cell.y, current_cell.left_moves, current_cell.right_moves, true ); // Upwards Enqueue(current_cell.x, current_cell.y - 1, current_cell.left_moves + 1, current_cell.right_moves, false ); // Downwards Enqueue(current_cell.x, current_cell.y + 1, current_cell.left_moves, current_cell.right_moves + 1, false ); } } static void Main() { // Input grid size, starting position, and allowed // moves n = 4; m = 5; startRow = 2; startCol = 1; L = 1; R = 2; // Input the grid int [, ] inputGrid = { { 0, 0, 0, 0, 0 }, { 0, 1, 1, 1, 0 }, { 0, 0, 0, 1, 1 }, { 1, 0, 0, 0, 0 } }; // 1-based indexing for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { grid[i, j] = inputGrid[i, j]; } } // Execute 0-1 breadth-first search BFS(); // Output the number of reachable cells Console.WriteLine(reachable_cells); } } // This code is contributed by Susobhan Akhuli |
Javascript
// JavaScript code for the above approach: // Maximum size for the grid const MAX_N = 2010; let grid = []; let visited = []; let n, m, L, R, startRow, startCol, reachableCells = 0; // Structure to represent a cell in the grid class Cell { constructor(x, y, leftMoves, rightMoves) { this .x = x; this .y = y; this .leftMoves = leftMoves; this .rightMoves = rightMoves; } } // Using arrays as queues for 0-1 BFS let dq = []; // Function to add a cell to the deque based on the direction function enqueue(x, y, leftMoves, rightMoves, isFront) { if (x >= 0 && y >= 0 && x < n && y < m && grid[x][y] === 0 && !visited[x][y] && leftMoves <= L && rightMoves <= R ) { visited[x][y] = true ; if (isFront) { dq.unshift( new Cell(x, y, leftMoves, rightMoves)); } else { dq.push( new Cell(x, y, leftMoves, rightMoves)); } } } // 0-1 BFS to find reachable cells function bfs() { dq.unshift( new Cell(startRow, startCol, 0, 0)); // Starting cell visited[startRow][startCol] = true ; while (dq.length > 0) { let currentCell = dq.shift(); reachableCells++; // Explore neighboring cells in all four directions // Left enqueue(currentCell.x - 1, currentCell.y, currentCell.leftMoves, currentCell.rightMoves, true ); // Right enqueue(currentCell.x + 1, currentCell.y, currentCell.leftMoves, currentCell.rightMoves, true ); // Upwards enqueue(currentCell.x, currentCell.y - 1, currentCell.leftMoves + 1, currentCell.rightMoves, false ); // Downwards enqueue(currentCell.x, currentCell.y + 1, currentCell.leftMoves, currentCell.rightMoves + 1, false ); } } // Input grid size, starting position, // and allowed moves n = 4; m = 5; startRow = 2; startCol = 1; L = 1; R = 2; // Input the grid let inputGrid = [ [0, 0, 0, 0, 0], [0, 1, 1, 1, 0], [0, 0, 0, 1, 1], [1, 0, 0, 0, 0] ]; // Initialize grid and visited arrays for (let i = 0; i < n; i++) { grid.push(inputGrid[i].slice()); visited.push( new Array(m).fill( false )); } // Execute 0-1 breadth-first search bfs(); // Output the number of reachable cells console.log(reachableCells); |
10
Time Complexity: O(N * M), where N is the number of rows and M is the number of columns.
Auxiliary Space: O(N * M) due to the storage needed for the visited array and the deque used in the breadth-first search.