All problems

Number of Enclaves

Medium · graph traversal

You are given a map as a rectangular grid of integers, grid. A cell holding 1 is land and a cell holding 0 is sea.

You can walk from a land cell to the land cell directly above, below, left or right of it. You cannot move diagonally and you cannot step onto sea.

A land cell is enclosed if no walk over land starting from it ever reaches a land cell on the edge of the grid (the first or last row, or the first or last column). A land cell that is itself on the edge is never enclosed.

Return the number of enclosed land cells. If there are none, return 0.

Examples

Example 1

Input: grid = [[0, 0, 0, 0], [1, 0, 1, 0], [0, 1, 1, 0], [0, 0, 0, 0]]

Output: 3

The land cell at the left edge can walk nowhere else. The three connected cells in the middle never touch the edge, so they are enclosed.

Example 2

Input: grid = [[0, 1, 1, 0], [0, 0, 1, 0], [0, 0, 1, 0], [0, 0, 0, 0]]

Output: 0

The land touches the top edge, so every cell connected to it can reach the edge.

Example 3

Input: grid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]

Output: 1

The only land cell is surrounded by sea and is not on the edge.

Constraints