Simulating Barriers in a Grid

This challenge asks you to simulate the placement and effect of barriers within a grid. Barriers restrict movement, and understanding how to represent and manage them is fundamental in pathfinding, game development, and various simulation scenarios. You'll be given a grid and a set of barrier coordinates, and your task is to determine which cells are reachable from a starting point, considering the barriers.

Problem Description

You are given a 2D grid represented as a list of lists, where each inner list represents a row. The grid contains only 0s and 1s. A 0 represents an open cell, and a 1 represents a barrier. You are also given a starting coordinate (row, col) and a list of barrier coordinates, which are used to initialize the grid. Your task is to implement a function that determines all reachable cells from the starting coordinate, moving only up, down, left, or right (no diagonal movement).

What needs to be achieved:

• Initialize a grid with the given dimensions and barrier coordinates.
• Perform a breadth-first search (BFS) or depth-first search (DFS) starting from the given coordinate.
• Identify all cells reachable from the starting coordinate without passing through a barrier.
• Return a list of tuples, where each tuple represents the (row, col) coordinates of a reachable cell.

Key Requirements:

• The grid is rectangular.
• The starting coordinate is within the bounds of the grid.
• Barrier coordinates are within the bounds of the grid.
• The grid is immutable after initialization.
• The function should handle cases where the starting coordinate is a barrier.

Expected Behavior:

The function should return a list of (row, col) tuples representing the reachable cells. The starting cell should be included in the list if it's not a barrier. The order of the reachable cells in the output list does not matter.

Edge Cases to Consider:

• Empty grid.
• No barriers.
• Starting coordinate is a barrier.
• No reachable cells (completely surrounded by barriers).
• Grid with only one cell.

Examples

Example 1:

Input: grid_size = (3, 3), start = (0, 0), barriers = [(1, 1), (2, 0)]
Output: [(0, 0), (0, 1), (0, 2), (1, 0), (1, 2), (2, 2)]
Explanation: Starting from (0, 0), we can reach (0, 0), (0, 1), (0, 2), (1, 0), (1, 2), and (2, 2) without hitting the barriers at (1, 1) and (2, 0).

Example 2:

Input: grid_size = (2, 2), start = (0, 0), barriers = [(0, 1), (1, 0)]
Output: [(0, 0)]
Explanation: Starting from (0, 0), we are blocked by barriers at (0, 1) and (1, 0), so only (0, 0) is reachable.

Example 3:

Input: grid_size = (2, 2), start = (0, 0), barriers = [(0, 0)]
Output: []
Explanation: The starting cell (0, 0) is a barrier, so no cells are reachable.

Constraints

• grid_size will be a tuple of two integers representing the number of rows and columns (rows, cols), where 1 <= rows, cols <= 100.
• start will be a tuple of two integers representing the starting row and column (row, col), where 0 <= row < rows and 0 <= col < cols.
• barriers will be a list of tuples, where each tuple represents the row and column of a barrier (row, col), where 0 <= row < rows and 0 <= col < cols.
• The number of barriers will be between 0 and rows * cols inclusive.
• The solution should have a time complexity of O(rows * cols) in the worst case.

Notes

• Consider using Breadth-First Search (BFS) or Depth-First Search (DFS) to explore the grid.
• Keep track of visited cells to avoid cycles.
• You can represent the grid as a 2D list (list of lists).
• Think about how to efficiently check if a cell is within the grid boundaries.
• The grid is initialized with 0s and then barriers are placed. You don't need to handle any other values in the grid.