1254. Number of Closed Islands #

Problem #

Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.

Return the number of closed islands.

Example 1:

Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation: 
Islands in gray are closed because they are completely surrounded by water (group of 1s).

Example 2:

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

Example 3:

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

Constraints:

• 1 <= grid.length, grid[0].length <= 100
• 0 <= grid[i][j] <=1

Problem Summary #

There is a 2D matrix grid, where each position is either land (denoted by 0) or water (denoted by 1). Starting from a piece of land, each time we can move to an adjacent area in one of the 4 directions: up, down, left, and right. All land areas that can be reached are called an “island”. If an island is completely surrounded by water, meaning all adjacent areas around the land boundary in the up, down, left, and right directions are water, then it is called a “closed island”. Return the number of closed islands.

Note:

• 1 <= grid.length, grid[0].length <= 100
• 0 <= grid[i][j] <=1

Solution Ideas #

• Given a map, 1 represents seawater and 0 represents land. The task is to find the total number of land areas that are surrounded by seawater on all four sides.
• The solution idea for this problem is exactly the same as Problem 200. The only difference is that this problem requires all four sides to be surrounded by seawater, while in Problem 200, land can be adjacent to the edge of the map. In this problem, land adjacent to the edge of the map cannot be counted in the final result.

Code #

package leetcode

func closedIsland(grid [][]int) int {
	m := len(grid)
	if m == 0 {
		return 0
	}
	n := len(grid[0])
	if n == 0 {
		return 0
	}
	res, visited := 0, make([][]bool, m)
	for i := 0; i < m; i++ {
		visited[i] = make([]bool, n)
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			isEdge := false
			if grid[i][j] == 0 && !visited[i][j] {
				checkIslands(grid, &visited, i, j, &isEdge)
				if !isEdge {
					res++
				}

			}
		}
	}
	return res
}

func checkIslands(grid [][]int, visited *[][]bool, x, y int, isEdge *bool) {
	if (x == 0 || x == len(grid)-1 || y == 0 || y == len(grid[0])-1) && grid[x][y] == 0 {
		*isEdge = true
	}
	(*visited)[x][y] = true
	for i := 0; i < 4; i++ {
		nx := x + dir[i][0]
		ny := y + dir[i][1]
		if isIntInBoard(grid, nx, ny) && !(*visited)[nx][ny] && grid[nx][ny] == 0 {
			checkIslands(grid, visited, nx, ny, isEdge)
		}
	}
	*isEdge = *isEdge || false
}

func isIntInBoard(board [][]int, x, y int) bool {
	return x >= 0 && x < len(board) && y >= 0 && y < len(board[0])
}