Q419-甲板上的战舰-中等-深度/宽度优先搜索

419. 甲板上的战舰

Question

给定一个二维的甲板， 请计算其中有多少艘战舰。 战舰用 'X'表示，空位用 '.'表示。 你需要遵守以下规则：

给你一个有效的甲板，仅由战舰或者空位组成。 战舰只能水平或者垂直放置。换句话说,战舰只能由 1xN (1 行, N 列)组成，或者 Nx1 (N 行, 1 列)组成，其中N可以是任意大小。 两艘战舰之间至少有一个水平或垂直的空位分隔 - 即没有相邻的战舰。

输入二维数组board

输出有多少战舰

Example 1:

X..X
...X
...X

输出：2

Note:

不用考虑无效样本

...X
XXXX
...X

Approach 1: 深度优先搜索+递归

简单处理，DFS越来越熟练了

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        def DFS(cur_i,cur_j):
            if 0<=cur_i and cur_i<r and 0<=cur_j and cur_j<c and board[cur_i][cur_j] == 'X':
                board[cur_i][cur_j] = "."
                for di,dj in [(-1,0),(1,0),(0,-1),(0,1)]:
                    DFS(cur_i+di,cur_j+dj)

        r,c = len(board),len(board[0])
        ans=0
        for i in range(r):
            for j in range(c):
                if board[i][j] == 'X':
                    ans+=1
                    DFS(i,j)

        return ans

复杂度分析

• 时间复杂度：。其中 R 是给定网格中的行数，C 是列数。我们访问每个网格最多一次。
• 空间复杂度：