0419. Battleships in a Board

题目信息

题号:

0419

难度:

Medium

主题:

字符矩阵、直线战舰、四邻接分离、数量统计

原题:

LeetCode 0419

重点:

每艘战舰是水平或竖直连续 X、不能弯折、不同战舰不在上下左右方向相邻、返回舰船数量

题目重述

给定只包含字符 'X' 和 '.' 的矩阵 board。'X' 表示战舰的一部分,'.' 表示空格。每艘战舰由同一行或同一列中的一个或多个连续 'X' 组成,不能弯折。

题目保证输入棋盘有效:两艘不同战舰之间不会在上下或左右方向直接相邻。返回棋盘中的战舰数量。矩阵行列数均位于 [1, 200]。函数不应修改输入棋盘;题目的进阶要求只扫描一次并使用常数额外空间。

自建示例

同时包含水平、竖直和单格战舰:

输入:board = [["X","X",".","."],
                [".",".",".","X"],
                ["X",".",".","X"]]
输出:3
解释:第一行前两个 X 构成一艘水平战舰;最右列后两个 X 构成一艘竖直战舰;左下角单独的 X 是第三艘战舰。

全为空格:

输入:board = [[".","."],[".","."]]
输出:0
解释:棋盘中没有字符 X,因此没有战舰。

只数每艘战舰的左上端点

输入保证不同战舰不在上下左右相邻,因此一艘水平或竖直战舰的第一个 X 不会在它的上方或左方紧邻另一个 X。扫描每个格子时,只有当前格为 X 且上方、左方都不是 X,才把它视为一艘新战舰;同一战舰后续的横向或纵向格子都会被跳过。

C++ 实现

class Solution {
public:
    int countBattleships(std::vector<std::vector<char>>& board) {
        int rows = static_cast<int>(board.size());
        int cols = static_cast<int>(board[0].size());
        int result = 0;
        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                if (board[row][col] != 'X') continue;
                if (row > 0 && board[row - 1][col] == 'X') continue;
                if (col > 0 && board[row][col - 1] == 'X') continue;
                ++result;
            }
        }
        return result;
    }
};

代码分析

有效输入保证一艘战舰不会从左方和上方同时以另一艘船接入,所以“没有上邻居且没有左邻居”恰好只命中每艘船一次;算法不修改棋盘。时间复杂度为 O(mn),额外空间为 O(1)。