【力扣】419:甲板上的战舰 |BFS_战舰 力扣

题目描述

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

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

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

来源：力扣（LeetCode）

算法思路

标准版 青春版

算是广度优先搜索吧，只是因为是战舰，直的，所以不许用扩散搜索，而是朝一个方向搜索。
所以是标准BFS的修改版本。

class Solution:
    def countBattleships(self, board) -> int:
        m,n=len(board),len(board[0])
        res=0
        for x in range(m):
            for y in range(n):
                if board[x][y]=='X':
                    res+=1
                    board[x][y]='.'
                    i,j=x,y
                    if i+1<m and board[i+1][j]=='X':
                        while i+1<m and board[i+1][j]=='X':
                            board[i+1][j]='.'
                            i+=1
                    elif j+1<n and board[i][j+1]=='X':
                        while j+1<n and board[i][j+1]=='X':
                            board[i][j+1]='.'
                            j+=1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

进阶 PLUS

一次搞定，常数额外空间，还不可以修改甲板，我是没想到

但是看了一眼评论我傻了……
每遍历到一个X判断其上方或左方是不是X，如果不是就表示这是一个新战舰。

我现在在怀疑自己是**。

class Solution:
    def countBattleships(self, board) -> int:
        m,n=len(board),len(board[0])
        res=0
        for x in range(m):
            for y in range(n):
                if board[x][y]=='X':
                    if x-1>=0 and board[x-1][y]=='X':
                        continue
                    if y-1>=0 and board[x][y-1]=='X':
                        continue
                    res+=1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13

执行用时 :84 ms, 在所有 Python3 提交中击败了77.47%的用户
内存消耗 :14.2 MB, 在所有 Python3 提交中击败了100.00%的用户