LeetCode 529. 扫雷游戏

Categories:

题目描述
思路分析
1. 解法一：DFS 模拟展开（推荐）
相似题目

题目描述

✅ 529. 扫雷游戏

思路分析

解法一：DFS 模拟展开（推荐）

核心思路：

若点击到地雷，直接标记为 X。

否则统计周围 8 个方向的地雷数。

若周围有雷，当前格子标记为数字；否则标记为 B 并继续 DFS 扩展相邻格子。

复杂度分析：

时间复杂度：O(mn)，其中 m、n 表示棋盘行列。

空间复杂度：O(mn)，最坏情况下递归栈展开整个棋盘。

class Solution {
    private static final int[] DIRS = {-1, 0, 1};

    public char[][] updateBoard(char[][] board, int[] click) {
        int r = click[0];
        int c = click[1];

        if (board[r][c] == 'M') {
            board[r][c] = 'X';
            return board;
        }

        dfs(board, r, c);
        return board;
    }

    private void dfs(char[][] board, int r, int c) {
        if (board[r][c] != 'E') {
            return;
        }

        int mines = countMines(board, r, c);
        if (mines > 0) {
            board[r][c] = (char) ('0' + mines);
            return;
        }

        board[r][c] = 'B';

        for (int dr : DIRS) {
            for (int dc : DIRS) {
                if (dr == 0 && dc == 0) {
                    continue;
                }

                int nr = r + dr;
                int nc = c + dc;
                if (nr < 0 || nr >= board.length || nc < 0 || nc >= board[0].length) {
                    continue;
                }

                dfs(board, nr, nc);
            }
        }
    }

    private int countMines(char[][] board, int r, int c) {
        int count = 0;
        for (int dr : DIRS) {
            for (int dc : DIRS) {
                if (dr == 0 && dc == 0) {
                    continue;
                }

                int nr = r + dr;
                int nc = c + dc;
                if (nr < 0 || nr >= board.length || nc < 0 || nc >= board[0].length) {
                    continue;
                }

                if (board[nr][nc] == 'M') {
                    count++;
                }
            }
        }
        return count;
    }
}

func updateBoard(board [][]byte, click []int) [][]byte {
	r, c := click[0], click[1]
	if board[r][c] == 'M' {
		board[r][c] = 'X'
		return board
	}

	dfsMines(board, r, c)
	return board
}

func dfsMines(board [][]byte, r int, c int) {
	if board[r][c] != 'E' {
		return
	}

	mines := countMines(board, r, c)
	if mines > 0 {
		board[r][c] = byte('0' + mines)
		return
	}

	board[r][c] = 'B'

	for dr := -1; dr <= 1; dr++ {
		for dc := -1; dc <= 1; dc++ {
			if dr == 0 && dc == 0 {
				continue
			}
			nr := r + dr
			nc := c + dc
			if nr < 0 || nr >= len(board) || nc < 0 || nc >= len(board[0]) {
				continue
			}
			dfsMines(board, nr, nc)
		}
	}
}

func countMines(board [][]byte, r int, c int) int {
	count := 0
	for dr := -1; dr <= 1; dr++ {
		for dc := -1; dc <= 1; dc++ {
			if dr == 0 && dc == 0 {
				continue
			}
			nr := r + dr
			nc := c + dc
			if nr < 0 || nr >= len(board) || nc < 0 || nc >= len(board[0]) {
				continue
			}
			if board[nr][nc] == 'M' {
				count++
			}
		}
	}
	return count
}

相似题目

题目	难度	考察点
200. 岛屿数量	中等	DFS/BFS
695. 岛屿的最大面积	中等	DFS/BFS
417. 太平洋大西洋水流问题	中等	DFS
542. 01 矩阵	中等	BFS
130. 被围绕的区域	中等	DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/39327240