甲板上的战舰

力扣 419. 甲板上的战舰

题目说明

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

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

提示：

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

示例

示例 1:

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

示例 2:

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

笔者理解

此题是一道数组算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题我们只需按照左上角计算战舰即可，让我们来看看具体如何实现的吧。

实现

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

        boolean[][] ticks = new boolean[m][n];
        int result = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!ticks[i][j] && board[i][j] == 'X') {
                    // 只统计左上角
                    result++;
                    tick(board, ticks, i, j);
                }
            }
        }

        return result;
    }

    public void tick(char[][] board, boolean[][] ticks, int i, int j) {
        int m = board.length;
        int n = board[0].length;

        // 越界或者为空地则回退
        if (i >= m || j >= n || board[i][j] == '.') {
            return ;
        }

        ticks[i][j] = true;

        // 只向下向右判断
        tick(board, ticks, i + 1, j);
        tick(board, ticks, i, j + 1);
    }

}