文章目录

• 一【题目类别】
• 二【题目难度】
• 三【题目编号】
• 四【题目描述】
• 五【题目示例】
• 六【解题思路】
• 七【题目提示】
• 八【题目进阶】
• 九【时间频度】
• 十【代码实现】
• 十一【提交结果】

一【题目类别】

• 深度优先搜索

二【题目难度】

• 中等

三【题目编号】

• 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.lengthm == board.lengthm==board.length
• n==board[i].lengthn == board[i].lengthn==board[i].length
• 1<=m,n<=2001 <= m, n <= 2001<=m,n<=200
• board[i][j]是′.′或′X′board[i][j] 是 '.' 或 'X'board[i][j]是′.′或′X′

八【题目进阶】

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

九【时间频度】

• 时间复杂度：O(m∗n)O(m*n)O(m∗n)，其中m,nm,nm,n分别为传入的图的行和列
• 空间复杂度：O(1)O(1)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;ifor(int j = 0;jif((board[i][j] == 'X') && (i == 0 || board[i - 1][j] == '.') && (j == 0 || board[i][j - 1] == '.')){count++;}}}return count;}
}

2. C语言版

int countBattleships(char** board, int boardSize, int* boardColSize)
{int m = boardSize;int n = boardColSize[0];int count = 0;for(int i = 0;ifor(int j = 0;jif((board[i][j] == 'X') && (i == 0 || board[i - 1][j] == '.') && (j == 0 || board[i][j - 1] == '.')){count++;}}}return count;
}

3. Python语言版

class Solution:def countBattleships(self, board: List[List[str]]) -> int:m = len(board)n = len(board[0])count = 0for 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+=1return count

4. C++语言版

class Solution {
public:int countBattleships(vector>& board) {int m = board.size();int n = board[0].size();int count = 0;for(int i = 0;ifor(int j = 0;jif((board[i][j] == 'X') && (i == 0 || board[i - 1][j] == '.') && (j == 0 || board[i][j - 1] == '.')){count++;}}}return count;}
};

十一【提交结果】

1. Java语言版
   

2. C语言版
   

3. Python语言版
   

4. C++语言版