419.甲板上的战舰

1、题干

给你一个大小为 m x n 的矩阵 board 表示甲板，其中，每个单元格可以是一艘战舰 'X' 或者是一个空位 '.' ，返回在甲板 board 上放置的 战舰 的数量。

战舰 只能水平或者垂直放置在 board 上。换句话说，战舰只能按 1 x k（1 行，k 列）或 k x 1（k 行，1 列）的形状建造，其中 k 可以是任意大小。两艘战舰之间至少有一个水平或垂直的空位分隔 （即没有相邻的战舰）。

 

示例 1：

输入：board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
输出：2

示例 2：

输入：board = [["."]]
输出：0

 

提示：

• m == board.length
• n == board[i].length
• 1 <= m, n <= 200
• board[i][j] 是 '.' 或 'X'

 

进阶：你可以实现一次扫描算法，并只使用 O(1) 额外空间，并且不修改 board 的值来解决这个问题吗？

执行结果

解法1-寻找船头

由于战舰只能水平或者垂直放置在board上，那就意味着船头位置的左边和上边必然是空位。因此只要双循环遍历整个board矩阵，遇到船头则战舰数量加一。

同理可以寻找船尾，船尾的右边和下边必然是空位。

代码

一行强迫症写法

var countBattleships = function (board) {
    return board.reduce((acc, cur, i) => acc + cur.filter((c, j) => c === 'X' && board[i][j - 1] !== 'X' && (!i || board[i - 1][j] !== 'X')).length, 0);
};

常规写法

var countBattleships = function (board) {
    let res = 0;

    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            if (board[i][j] == 'X' && board[i][j - 1] !== 'X' && (!i || board[i - 1][j] !== 'X')) res++;
        }
    }

    return res;
};

解法2-DFS

双循环遍历整个board矩阵，遇到战舰则战舰数量加一，然后深度遍历战舰所占位置，把遍历过的战舰位置修改成空位避免重复遍历。

代码

var countBattleships = function (board) {
    let res = 0;
    function dfs(i, j) {
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] !== 'X') return;

        board[i][j] = '.';
        dfs(i + 1, j);
        dfs(i - 1, j);
        dfs(i, j + 1);
        dfs(i, j - 1);
    }

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

    return res;
};