419 甲板上的战舰（dfs、分析）_战舰数独题目

1. 问题描述：

给定一个二维的甲板， 请计算其中有多少艘战舰。 战舰用 'X'表示，空位用 '.'表示。 你需要遵守以下规则：
给你一个有效的甲板，仅由战舰或者空位组成。
战舰只能水平或者垂直放置。换句话说,战舰只能由 1xN (1 行, N 列)组成，或者 Nx1 (N 行, 1 列)组成，其中N可以是任意大小。
两艘战舰之间至少有一个水平或垂直的空位分隔 - 即没有相邻的战舰。

示例 :

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

在上面的甲板中有2艘战舰。

无效样例 :

...X
XXXX
...X

你不会收到这样的无效甲板 - 因为战舰之间至少会有一个空位将它们分开。

进阶:

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

2. 思路分析：

① 分析题目可以知道这个是一个连通性检测的问题，我们的任务是是要求解出图中联通块的数目，所以最容易想到的是dfs，因为dfs是可以将所有联通的区域一次搜索到，我们可以在搜索的时候标记一下搜索的位置，也就是将访问过的位置置为"." ，最后统一下dfs搜索过的次数那么就是联通块的数目了。

② 第二个想法是当我们在图中遇到"X"的时候我们需要判断当前位置的左边与上边是否是"X"，假如是"X"我们不进行计数，最后将计数结果返回即可。

3. 代码如下：

dfs:

from typing import List
 
 
class Solution:
    def dfs(self, board: List[List[str]], r: int, c: int, pos: List[List[str]]):
        board[r][c] = "."
        for i in range(4):
            x = r + pos[i][0]
            y = c + pos[i][1]
            if 0 <= x < len(board) and 0 <= y < len(board[0]) and board[x][y] == "X":
                self.dfs(board, x, y, pos)
 
    # 类似于岛屿问题所以可以使用dfs来解决
    def countBattleships(self, board: List[List[str]]) -> int:
        pos = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        res = 0
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == "X":
                    self.dfs(board, i, j, pos)
                    res += 1
        return res

循环遍历：

from typing import List
 
 
class Solution:
 
    def countBattleships(self, board: List[List[str]]) -> int:
        res = 0
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == "X":
                    if (j > 0 and board[i][j - 1]) == "X" or (i > 0 and board[i - 1][j] == "X"):
                        continue
                    res += 1
        return res