Land Regions on a Map

Medium

A map is given as a rectangular grid terrain with m rows and n columns. Each cell is the string '1' (land) or '0' (water). A land region is a group of '1' cells connected through horizontal or vertical neighbours; touching diagonally does not count. Everything outside the grid is water. Return the number of separate land regions.

Example 1

terrain=[['1', '0', '1'], ['1', '0', '0'], ['0', '1', '1']] → 3

Three regions: the two '1's in the left column, the lone '1' in the top-right corner and the pair at the bottom. Cells touching only diagonally are not joined.

Example 2

terrain=[['1', '1', '1'], ['1', '0', '1'], ['1', '1', '1']] → 1

The ring of land around a single water cell is one region.

Example 3

terrain=[['0', '0']] → 0

Constraints

1 ≤ m, n ≤ 300
All rows have the same number of cells
Every cell 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 Union Find Array Matrix

Similar problems

Drain the Landlocked Ponds Medium Largest Forest Patch Medium A Board Cut by Slashes Medium Landlocked Land Cells Medium Route With the Highest Bottleneck Medium

Input

terrain=[['1', '0', '1'], ['1', '0', '0'], ['0', '1', '1']]

Expected

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