力扣每日一题(十二——甲板上的战舰）_甲板上的战舰 csdn

仅以此纪录每日LeetCode所刷题目

题目描述：

示例：

思路：

这道题一开始想到的思路是使用深度优先遍历算法来求解，但仔细读题之后发现这样做会比较麻烦，因为战舰只是横向排序或者纵向排序，因此我们不需要像深度优先遍历一样每次向四个方向同时进行搜索。在进行网格搜索的时候，每当我们遇到网格中的字符为“X”(代表此处有战舰时)，我们只需要判断这个战舰的左面和上面是否存在战舰即可，若存在则代表这个网格存在于这个战舰的一行或者一列中。当这个战舰的左面和上面不存在战舰，则将计数器加一即可。

代码：

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        def dfs(i,j,board):
            board[i][j] = "x"
            if i > 0 and board[i-1][j] == "X":
                dfs(i-1,j,board)
            if i > 0 and board[i][j-1] == "X":
                dfs(i,j-1,board)
        count = 0
        row = len(board)
        col = len(board[0])
        for i in range(row):
            for j in range(col):
                if board[i][j] == "X":
                    if i>0 and board[i-1][j] == "X":
                        continue
                    if j>0 and board[i][j-1] == "X":
                        continue
                    count += 1
        return count

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        def dfs(i,j,board):
            board[i][j] = "x"
            if i > 0 and board[i-1][j] == "X":
                dfs(i-1,j,board)
            if i > 0 and board[i][j-1] == "X":
                dfs(i,j-1,board)
        count = 0
        row = len(board)
        col = len(board[0])
        for i in range(row):
            for j in range(col):
                if board[i][j] == "X":
                    if i<(len(board)-1) and board[i+1][j] == "X":
                        continue
                    if j<(len(board[0])-1) and board[i][j+1] == "X":
                        continue
                    count += 1
        return count