【LeetCode每日一题】——419.甲板上的战舰

一【题目类别】

• 深度优先搜索

二【题目难度】

• 中等

三【题目编号】

• 419.甲板上的战舰

四【题目描述】

• 给你一个大小为 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

六【解题思路】

• 本题可以用深度优先搜索直接解决，比较简单，但是在这里提供一种比较巧妙地解法：
• 通过分析题目我们可以发现，每个战舰之间都要么上下隔着海水，要么左右隔着海水，也就是没有相邻的战舰，并且战舰要么都是横着的，要么都是竖着的，所以每个战舰的开头的左面和上面一定是都是海水，那么我们只需要搜索每艘战舰的开头就行了：
  • 如果当前位置是’X’
  • 并且其左边和右边都是’.'，说明这就是一艘战舰的起始位置，数量加一
• 计算得到多少战舰的开头，就能得到战舰的数量
• 最后返回结果即可

七【题目提示】

• $m==board.length$
• $n==board[i].length$
• $1<=m,n<=200$
• $board[i][j]{是}^{\prime }{.}^{\prime }{或}^{\prime }{X}^{\prime }$

八【题目进阶】

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

九【时间频度】

• 时间复杂度：$O(m\ast n)$，其中$m,n$分别为传入的图的行和列
• 空间复杂度：$O(1)$

十【代码实现】

1. Java语言版

class Solution {
    public int countBattleships(char[][] board) {
        int m = board.length;
        int n = board[0].length;
        int count = 0;
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if((board[i][j] == 'X') && (i == 0 || board[i - 1][j] == '.') && (j == 0 || board[i][j - 1] == '.')){
                    count++;
                }
            }
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2. C语言版

int countBattleships(char** board, int boardSize, int* boardColSize)
{
    int m = boardSize;
    int n = boardColSize[0];
    int count = 0;
    for(int i = 0;i<m;i++)
    {
        for(int j = 0;j<n;j++)
        {
            if((board[i][j] == 'X') && (i == 0 || board[i - 1][j] == '.') && (j == 0 || board[i][j - 1] == '.'))
            {
                count++;
            }
        }
    }
    return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3. Python语言版

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        m = len(board)
        n = len(board[0])
        count = 0
        for i in range(0,m):
            for j in range(0,n):
                if (board[i][j] == 'X') and (i == 0 or board[i - 1][j] == '.') and (j == 0 or board[i][j - 1] == '.'):
                    count+=1
        return count
1
2
3
4
5
6
7
8
9
10

4. C++语言版

class Solution {
public:
    int countBattleships(vector<vector<char>>& board) 
    {
        int m = board.size();
        int n = board[0].size();
        int count = 0;
        for(int i = 0;i<m;i++)
        {
            for(int j = 0;j<n;j++)
            {
                if((board[i][j] == 'X') && (i == 0 || board[i - 1][j] == '.') && (j == 0 || board[i][j - 1] == '.'))
                {
                    count++;
                }
            }
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

十一【提交结果】

1. Java语言版
   

2. C语言版
   

3. Python语言版
   

4. C++语言版