974. Split the Island
A survey map grid marks land with 1 and water with 0. Land cells that share a side (up, down, left or right, not diagonals) belong to the same island. The map counts as split when it does not contain exactly one island, meaning it has no land at all or at least two separate islands.
Each day the sea can flood one single land cell, turning it into water. Return the minimum number of days needed to make the map split. If it is split already, return 0.
Example 1
- Input:
- grid = [[1,1,0],[0,1,1]]
- Output:
- 1
- Explanation:
The four land cells form a zigzag; flooding the second cell of the top row cuts it into two pieces after one day.
Example 2
- Input:
- grid = [[0,0],[0,0]]
- Output:
- 0
- Explanation:
There is no land at all, so the map already has no single island and zero days are needed.
Example 3
- Input:
- grid = [[1,1],[1,1]]
- Output:
- 2
- Explanation:
No single flooded cell splits a solid 2 x 2 block, but flooding two diagonal cells leaves two cells that only touch at a corner, so two days.
Constraints
- 1 ≤ grid.length, grid[i].length ≤ 300
- grid[i][j] is 0 or 1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(m * n)
- Space
- O(m * n)