leetcode-go/leetcode/medium/529.minesweeper.go

func updateBoard(board [][]byte, click []int) [][]byte {
	y, x := click[0], click[1]
	if board[y][x] != 'E' {
		if board[y][x] == 'M' {
			board[y][x] = 'X'
		}
		return board
	}
	m, n := len(board), len(board[0])
	count := make([][]int, m)
	for i := range count {
		count[i] = make([]int, n)
	}
	cntAllMines(board, m, n, count)
	dfs(board, m, n, count, y, x)
	return board
}

func dfs(board [][]byte, m, n int, count [][]int, y, x int) {
	if count[y][x] == 0 {
		board[y][x] = 'B'
		for dy := -1; dy <= 1; dy++ {
			for dx := -1; dx <= 1; dx++ {
				ny, nx := y+dy, x+dx
				if 0 <= ny && ny < m && 0 <= nx && nx < n && board[ny][nx] == 'E' {
					dfs(board, m, n, count, ny, nx)
				}
			}
		}
	} else {
		board[y][x] = byte(count[y][x] + '0')
	}
}

func cntAllMines(board [][]byte, m, n int, count [][]int) {
	for y := 0; y < m; y++ {
		for x := 0; x < n; x++ {
			if board[y][x] == 'M' {
				for dy := -1; dy <= 1; dy++ {
					for dx := -1; dx <= 1; dx++ {
						ny, nx := y+dy, x+dx
						if 0 <= ny && ny < m && 0 <= nx && nx < n {
							count[ny][nx]++
						}
					}
				}
			}
		}
	}
}

func updateBoardMLE(board [][]byte, click []int) [][]byte { // BFS, MLE
	y, x, m, n := click[0], click[1], len(board), len(board[0])
	if board[y][x] != 'E' {
		if board[y][x] == 'M' {
			board[y][x] = 'X'
		}
		return board
	}
	queue := [][]int{[]int{y, x}}
	for len(queue) != 0 {
		y, x = queue[0][0], queue[0][1]
		queue = queue[1:]
		cnt := cntMines(board, m, n, y, x)
		if cnt == 0 {
			board[y][x] = 'B'
			for dy := -1; dy <= 1; dy++ {
				for dx := -1; dx <= 1; dx++ {
					ny, nx := y+dy, x+dx
					if 0 <= ny && ny < m && 0 <= nx && nx < n && board[ny][nx] == 'E' {
						queue = append(queue, []int{ny, nx})
					}
				}
			}
		} else {
			board[y][x] = byte(cnt + '0')
		}
	}
	return board
}

func cntMines(board [][]byte, m, n, y, x int) (cnt int) {
	for dy := -1; dy <= 1; dy++ {
		for dx := -1; dx <= 1; dx++ {
			ny, nx := y+dy, x+dx
			if 0 <= ny && ny < m && 0 <= nx && nx < n && board[ny][nx] == 'M' {
				cnt++
			}
		}
	}
	return
}