419.md

Battleships in a Board

Description

link

---

Solution

• 因为必然相连，所以只需要检查当前这个X上面和左边是否有'.'即可

---

Code

Complexity O(mn)

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        m = len(board)
        if m == 0: return 0
        n = len(board[0])
        count = 0
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'X':
                    if (i - 1 < 0 or board[i - 1][j] == '.') and (j - 1 < 0 or board[i][j - 1] == '.'):
                        count += 1
        return count