leetcode-go/medium/417.pacific-atlantic-water-flow.go

var dx []int = []int{1, 0, -1, 0}
var dy []int = []int{0, -1, 0, 1}

func pacificAtlantic(matrix [][]int) (res [][]int) {
	m := len(matrix)
	if m == 0 {
		return
	}
	n := len(matrix[0])
	if n == 0 {
		return
	}
	ocean := make([][]int, m)
	for i := 0; i < m; i++ {
		ocean[i] = make([]int, n)
	}
	for i := 0; i < m; i++ { // b10: pacific, b01: atlantic
		dfs(matrix, 2, 0, i, ocean, m, n)
		dfs(matrix, 1, n-1, i, ocean, m, n)
	}
	for i := 0; i < n; i++ {
		dfs(matrix, 2, i, 0, ocean, m, n)
		dfs(matrix, 1, i, m-1, ocean, m, n)
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if ocean[i][j] == 3 {
				res = append(res, []int{i, j})
			}
		}
	}
	return
}

func dfs(matrix [][]int, mask, x, y int, ocean [][]int, m, n int) {
	ocean[y][x] |= mask
	for i := 0; i < 4; i++ {
		nx, ny := x+dx[i], y+dy[i]
		if 0 <= nx && nx < n && 0 <= ny && ny < m && ocean[ny][nx]&mask == 0 && matrix[y][x] <= matrix[ny][nx] {
			dfs(matrix, mask, nx, ny, ocean, m, n)
		}
	}
}