LeetCode 419. 棋盘上的战舰

Categories:

题目描述
思路分析
1. 解法一：原地标记（推荐）
2. 解法二：深度优先搜索（DFS）
相似题目

题目描述

✅ 419. 棋盘上的战舰

思路分析

解法一：原地标记（推荐）

核心思路：

战舰占据棋盘上连续的一行或一列格子，只需统计战舰的数量，不需要区分每艘战舰的具体范围

关键观察：只统计每艘战舰的左上角格子（即战舰的起始格）

对于每个 'X' 格，若其上方或左方也是 'X'，则它不是左上角，跳过

遍历一遍矩阵，满足条件的格子数即为战舰总数

该方法无需额外空间，一次遍历即可完成

复杂度分析：

时间复杂度：O(m × n)，其中 m、n 分别为棋盘的行数和列数

空间复杂度：O(1)，不使用额外空间

class Solution {
    public int countBattleships(char[][] board) {
        int count = 0;
        int m = board.length;
        int n = board[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 跳过水域格
                if (board[i][j] == '.') {
                    continue;
                }

                // 若上方是 'X'，说明当前格不是战舰起始格
                if (i > 0 && board[i - 1][j] == 'X') {
                    continue;
                }

                // 若左方是 'X'，说明当前格不是战舰起始格
                if (j > 0 && board[i][j - 1] == 'X') {
                    continue;
                }

                count++;
            }
        }

        return count;
    }
}

func countBattleships(board [][]byte) int {
    count := 0
    m := len(board)
    n := len(board[0])

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            // 跳过水域格
            if board[i][j] == '.' {
                continue
            }

            // 若上方是 'X'，说明当前格不是战舰起始格
            if i > 0 && board[i-1][j] == 'X' {
                continue
            }

            // 若左方是 'X'，说明当前格不是战舰起始格
            if j > 0 && board[i][j-1] == 'X' {
                continue
            }

            count++
        }
    }

    return count
}

解法二：深度优先搜索（DFS）

核心思路：

遍历矩阵，遇到 'X' 时，通过 DFS 将整艘战舰的格子标记为已访问（改为 '.'）

每触发一次 DFS，战舰计数加一

该方法会修改原始棋盘，适合理解但不如解法一简洁

复杂度分析：

时间复杂度：O(m × n)，每个格子最多访问一次

空间复杂度：O(m × n)，递归栈最坏情况下深度为 m × n

class Solution {
    public int countBattleships(char[][] board) {
        int count = 0;

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'X') {
                    dfs(board, i, j);
                    count++;
                }
            }
        }

        return count;
    }

    private void dfs(char[][] board, int i, int j) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
            return;
        }

        if (board[i][j] != 'X') {
            return;
        }

        // 标记为已访问
        board[i][j] = '.';

        dfs(board, i + 1, j);
        dfs(board, i - 1, j);
        dfs(board, i, j + 1);
        dfs(board, i, j - 1);
    }
}

func countBattleships(board [][]byte) int {
    count := 0

    for i := 0; i < len(board); i++ {
        for j := 0; j < len(board[0]); j++ {
            if board[i][j] == 'X' {
                dfs(board, i, j)
                count++
            }
        }
    }

    return count
}

func dfs(board [][]byte, i, j int) {
    if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) {
        return
    }

    if board[i][j] != 'X' {
        return
    }

    // 标记为已访问
    board[i][j] = '.'

    dfs(board, i+1, j)
    dfs(board, i-1, j)
    dfs(board, i, j+1)
    dfs(board, i, j-1)
}

相似题目

题目	难度	考察点
200. 岛屿数量	中等	DFS/BFS、矩阵
130. 被围绕的区域	中等	DFS、矩阵
695. 岛屿的最大面积	中等	DFS、矩阵
463. 岛屿的周长	简单	矩阵遍历
1020. 飞地的数量	中等	DFS、矩阵
1905. 统计子岛屿	中等	DFS、矩阵

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/15657902