Landlocked Land Cells

Medium

A map is given as a matrix terrain of zeros and ones: 1 is land, 0 is water. A traveler can step from a land cell to an adjacent land cell horizontally or vertically, and from a cell on the edge of the map they can step off it entirely. Count the land cells from which the traveler can never leave the map.

Example 1

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

The three land cells in the middle are connected and never touch the edge, so they are trapped. The cells at (0, 0) and (2, 4) lie on the border.

Example 2

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

The five-cell island reaches the right edge through cell (2, 3), so every one of its cells can walk off the map.

Example 3

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

Constraints

1 ≤ number of rows, number of columns ≤ 500
Every cell of terrain 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 Land Regions on a Map Medium Largest Forest Patch Medium A Board Cut by Slashes Medium Route With the Highest Bottleneck Medium

Input

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

Expected

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