力扣每日一题 6/11 暴力搜索

419.甲板上的战舰[中等]

题目：

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

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

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

输出：2

示例 2：

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

输出：0

提示：

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

题目分析：

        这道题可能题目有点表达不清晰，会让人误以为只有在第1行的某个列和第1列的某行才能算数，其实并不是这个意思。他的意思是每个战舰都要和周围的分开，当他们相连接的时候是被看做一个战舰的，只有被隔开的两个战舰才被认为是两个战舰，然后搜查一共有多少艘战舰。

       最本质的思路就是暴力搜索，遍历一遍看看有几个符合题意的X，统计并返回即可。以下是代码实现：

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        a1,a2,res=len(board),len(board[0]),0  # a1是行  a2是列 res是战舰总数
        for i in range(a1):
            for j in range(a2):
                if (j==0 and board[i][j]=='X' and ((i>0 and board[i-1][j]!='X') or (i==0))) or (j!=0 and board[i][j]=='X' and board[i][j-1]=='.' and ((i>0 and board[i-1][j]!='X') or (i==0))): res+=1
        return res

总结：

       这段代码通过遍历二维字符数组中的每个位置，并根据相邻字符的情况，判断该位置是否属于战舰，从而统计出二维字符数组中战舰的数量。以下是具体实现步骤：

1. 首先，获取二维字符数组 board 的行数和列数，分别赋值给变量 a1 和 a2，并初始化战舰总数变量 res 为 0。
   
2. 然后，使用两层循环遍历整个二维数组 board。外层循环控制行数，内层循环控制列数。
   
3. 在每次循环中，通过条件判断语句检查当前字符是否为 ‘X’，以及其前一个字符的情况，来判断当前位置是否属于战舰。具体的判断逻辑如下：

• 如果当前字符在第一列且为 ‘X’，且前一个字符不是 ‘X’（或当前字符在第一行），则将战舰总数 res 增加 1。
• 如果当前字符不在第一列且为 ‘X’，且当前字符的前一个字符是 ‘.’（表示战舰的左侧没有战舰），并且满足第一个条件（前一个字符不是 'X’或当前字符在第一行），则将战舰总数 res 增加 1。

4. 最后，返回统计得到的战舰总数 res。