难度: Medium
给你一个大小为 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.lengthn == board[i].length1 <= m, n <= 200board[i][j] 是 '.' 或 'X'进阶：你可以实现一次扫描算法，并只使用 O(1) 额外空间，并且不修改 board 的值来解决这个问题吗？
运行时间: 21 ms
内存: 18.2 MB
class Solution:
def countBattleships(self, board: List[List[str]]) -> int:
m = len(board)
n = len(board[0])
res = 0
for i in range(m):
for j in range(n):
if board[i][j] == 'X':
res += 1
board[i][j] = '.'
vert = i+1
hor = j+1
while vert < m and board[vert][j] == 'X':
board[vert][j] = '.'
vert += 1
while hor < n and board[i][hor] == 'X':
board[i][hor] = '.'
hor += 1
return res
这个题解采用了一次遍历的思路。从矩阵的左上角开始，遍历每个格子。当遇到一个战舰('X')时，将计数器加1，并将该格子标记为已访问('.')。然后向下和向右分别搜索，将连续的战舰格子都标记为已访问，直到遇到空位('.')或越界为止。这样可以确保每个战舰只被计数一次。
时间复杂度: O(m*n)
空间复杂度: O(1)
class Solution:
def countBattleships(self, board: List[List[str]]) -> int:
m = len(board)
n = len(board[0])
res = 0
for i in range(m):
for j in range(n):
if board[i][j] == 'X':
res += 1 # 发现一艘战舰，计数器加1
board[i][j] = '.' # 标记当前格子为已访问
# 向下搜索连续的战舰格子
vert = i + 1
while vert < m and board[vert][j] == 'X':
board[vert][j] = '.' # 标记为已访问
vert += 1
# 向右搜索连续的战舰格子
hor = j + 1
while hor < n and board[i][hor] == 'X':
board[i][hor] = '.' # 标记为已访问
hor += 1
return res # 返回战舰的数量
在遍历矩阵时，我们只在发现'X'的首个单元格时增加计数器，是因为我们的目标是计数战舰的总数，而不是单个方格。战舰是由连续的'X'组成的，因此，遇到'X'时，我们认为它可能是一个新的战舰的开始。通过从这点向下和向右搜索并标记连续的'X'，我们可以确保整艘战舰被处理，从而避免对同一战舰的重复计数。
只向下和向右搜索的原因是，我们从矩阵的左上角开始遍历到右下角。当我们在某个位置发现'X'时，该位置左边和上边的所有单元格已经被检查过，因此任何可能连接的战舰部分也应该已经被标记。因此，只需要检查当前位置右边和下边的单元格，从而有效避免重复工作且保持算法效率。
直接在原数据上进行修改确实可能对其他操作产生影响，如需重复运行算法或进行并行处理时可能会遇到问题。因为一旦原始数据被修改，未来的任何算法或操作都将基于已经改变的数据，这可能导致错误的结果。通常，若原数据需要保留，则应考虑使用额外的数据结构来标记已访问的单元格，或在开始处理前复制一份数据用于操作。
在代码实现中，通过在while循环条件中检查边界，我们确保了不会越界。例如，在向下搜索时，我们检查'vert < m'，确保'vert'索引不会超过矩阵的行数。类似地，在向右搜索时，我们检查'hor < n'，确保'hor'索引不会超过矩阵的列数。这些条件确保了即使战舰位于边界上，代码也不会尝试访问不存在的矩阵元素，从而避免越界错误。