Daily DSA: Minimum Operations to Connect Grid Components (Hard)
Advertisement
Minimum Operations to Connect Grid Components
Problem Statement
You are given an $n \times m$ grid representing a map. Some cells are blocked (represented by 0) and some are open (represented by 1).
You are allowed to perform an operation: choose any blocked cell (0) and change it into an open cell (1).
Find the minimum number of operations required to ensure that all open cells (1) form a single connected component. Connectivity is defined as 4-directionally adjacent open cells (up, down, left, right).
If there are no open cells initially, return 0.
Examples
Example 1:
Input: grid = [
[1, 0, 1],
[0, 0, 0],
[1, 0, 1]
]
Output: 1
Explanation: Changing the center cell (1, 1) from 0 to 1 connects all four corner components into a single component.
Example 2:
Input: grid = [
[1, 1, 0],
[0, 1, 0],
[0, 0, 1]
]
Output: 2
Explanation: We can change (0, 2) and (1, 2) to 1 to connect everything.
Constraints
- $n == \text{grid.length}$
- $m == \text{grid[i].length}$
- $1 \le n, m \le 30$
grid[i][j]is either0or1.
Approach & Hints
- Identify Components: First, use BFS, DFS, or Disjoint Set Union (DSU) to find all existing connected components of
1s. If there are $\le 1$ components, the answer is0. - Exhaustive Search for Bridge Cells: Since the grid dimensions are small ($30 \times 30$), we can iterate over all
0cells and evaluate what happens if we change that0into a1. - Single vs Multiple Additions: Sometimes changing one
0is not enough. We might need to change up to 2 cells, or evaluate the minimum spanning tree of components where the edge weights are the Manhattan distances between components. - Optimization: For small grids, we can iterate through all pairs of
0cells or use a BFS-based shortest path approach treating components as nodes in a graph.
Advertisement