All problems

Number of Closed Islands

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 water.

An island is a group of land cells joined through shared edges: two land cells belong to the same island if you can walk from one to the other moving up, down, left or right over land only. Cells that touch only at a corner are not joined.

An island is closed if none of its cells is on the edge of the grid (the first or last row, or the first or last column). An island with even one cell on the edge is not closed.

Return the number of closed islands in grid. If there are none, return 0.

Examples

Example 1

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

Output: 1

The island of three cells in the upper left is surrounded by water. The single cell at the right edge is an island too, but it touches the edge, so it is not closed.

Example 2

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

Output: 0

Both islands have a cell in a corner of the grid.

Example 3

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

Output: 2

Two separate one-cell islands, neither on the edge.

Constraints