Split the Island

Hard

A map is a grid land of 0 (water) and 1 (land). An island is a maximal group of land cells connected through their sides (up, down, left, right). The map is **connected** if it contains exactly one island. Each day you may flood any one land cell, turning it into water. Return the fewest days after which the map is no longer connected. If it does not have exactly one island to begin with (zero or several), the answer is 0.

Example 1

land=[[1, 1, 1], [0, 1, 0], [0, 1, 0]] → 1

Flooding the middle cell (1, 1) breaks the island into three pieces, so one day is enough.

Example 2

land=[[1, 1], [1, 1]] → 2

Removing any single cell leaves an L of three cells, still one island. Removing two diagonal cells leaves two separate pieces: the answer is 2.

Example 3

land=[[1, 0, 1], [0, 0, 0]] → 0

Constraints

1 ≤ len(land), len(land[0]) ≤ 30
all rows of the grid have the same length
land[i][j] is 0 or 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Array Matrix Strongly Connected Component

Similar problems

Frame Around an Ink Blot Hard Longest Uphill Walk Hard Ball Into the Hole Hard Quarantine for Mould Hard Crossing at High Tide Hard

Input

land=[[1, 1, 1], [0, 1, 0], [0, 1, 0]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 76 tests on the server, hidden ones included.