Leetcode: 200. Number of Islands

numIslands.go

// Leetcode: 200. Number of Islands.
// https://leetcode.com/problems/number-of-islands/
// = = = = = = = = = = = = = =
// Accepted.
// Thanks God, Jesus Christ!
// = = = = = = = = = = = = = =
// Runtime: 4 ms, faster than 76.52% of Go online submissions for Number of
// Islands.
// Memory Usage: 6.1 MB, less than 28.58% of Go online submissions for Number
// of Islands.
// 2024.04.19 Daily Challenge.

package main

func numIslands(grid [][]byte) int {
	// Number of times BFS runs.
	ans := 0
	g := grid
	m, n := len(grid), len(grid[0])
	v := createV(m, n)
	for i := 0; i < m; i += 1 {
		for j := 0; j < n; j += 1 {
			if v[i][j] {
				continue
			}
			if '0' == g[i][j] {
				continue
			}
			ans += 1
			bfs(g, v, i, j)
		}
	}
	return ans
}
func createV(m, n int) [][]bool {
	v := make([][]bool, m)
	for i := 0; i < m; i += 1 {
		v[i] = make([]bool, n)
	}
	return v
}

func bfs(g [][]byte, v [][]bool, i, j int) {
	v[i][j] = true
	m, n := len(g), len(g[0])
	q := make([][2]int, 1)
	d := [][]int{
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1},
	}
	q[0] = [...]int{i, j}
	for 0 != len(q) {
		pair := q[0]
		q = q[1:]
		ci, cj := pair[0], pair[1]
		for _, dt := range d {
			ni, nj := ci+dt[0], cj+dt[1]
			if ni < 0 || nj < 0 || ni >= m || nj >= n {
				continue
			}
			if '0' == g[ni][nj] {
				continue
			}
			if v[ni][nj] {
				continue
			}
			q = append(q, [...]int{ni, nj})
			v[ni][nj] = true
		}
	}
}