663. Shortest Causeway
A flooded archipelago is drawn in the grid grid: 1 is dry ground and 0 is water. A landmass is a group of dry cells joined up, down, left or right; cells that only touch diagonally belong to different landmasses. The map is guaranteed to contain exactly two landmasses, and engineers want to merge them into one by building a causeway, that is, by converting some water cells into dry cells.
Return the smallest number of water cells that must be converted so that the two landmasses become a single connected landmass. Each landmass can be large and winding, so you should expect to run in time proportional to the number of cells rather than comparing every cell of one landmass with every cell of the other.
Example 1
- Input:
- grid = [[1,0,0,0],[0,0,0,0],[0,0,0,1]]
- Output:
- 4
- Explanation:
The landmasses are the single cells (0,0) and (2,3), five steps apart; four water cells in between must be converted.
Example 2
- Input:
- grid = [[1,1,0,0],[0,0,0,1],[0,0,0,1]]
- Output:
- 2
- Explanation:
The closest pair of dry cells is (0,1) and (1,3), so the two cells between them form the causeway: the answer is 2.
Example 3
- Input:
- grid = [[1,0,0],[0,1,0]]
- Output:
- 1
- Explanation:
The cells (0,0) and (1,1) touch only diagonally, so they are separate landmasses; converting one water cell such as (0,1) merges them.
Constraints
2 ≤ rows, cols ≤ 400
each cell is 0 or 1
the grid contains exactly two landmasses
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 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(rows*cols)
- Space
- O(rows*cols)