419.甲板上的战舰.md

419.甲板上的战舰

https://leetcode-cn.com/problems/battleships-in-a-board/

解法一：

思路:(借鉴discuss的)由于battleship形状必为矩形的特性,每个battleship都有一个最左上角(top-left)的元素,统计整个图中处于最左上角’X’的个数即可. 最左上角元素的’X’有何特征?其左侧和上方的元素都为’.’,换句话说,左侧或上方为’X’的肯定是battleship内的非最左上结点;此外为’.’的是battleship外部结点,根据这两条规则即可.

同理,统计”最左下“,”最右上“和”最右下“结点的思路也是可以的.

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        ship = 0    #战舰数
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == '.':    #空位
                    continue
                if i-1 >= 0 and board[i-1][j] == 'X':    #上方有X
                    continue
                if j-1 >= 0 and board[i][j-1] == 'X':    #左侧有X
                    continue
                ship += 1    #上方和左侧都没有X的，为最左上角
        return ship

解法二：并查集

两次遍历甲板，第一次求X个数cnt，作为并查集的连通分量数；第二次将X的上下左右X合并。最后看有几个连通分量

#并查集实现略
class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        m, n = len(board), len(board[0])
        visited = [[False]*n for _ in range(m)]
        cnt = 0
        #二维坐标转一维
        def flat(x, y):
            return x * n + y
        # 先遍历甲板，看有多少个X
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'X':
                    cnt += 1
        #节点数为m*n，但是连通分量数仅为X的个数
        uf = UnionFind(m*n, cnt)
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'X':
                    board[i][j] = '.'	#当前位置可以置'.'，避免重复访问
                    # 若上下左右有X，将其合并
                    if j > 0 and board[i][j-1] == 'X':
                        uf.union(flat(i, j), flat(i, j-1))
                    if j < n-1 and board[i][j+1] == 'X':
                        uf.union(flat(i, j), flat(i, j+1))
                    if i > 0 and board[i-1][j] == 'X':
                        uf.union(flat(i, j), flat(i-1, j))
                    if i < m-1 and board[i+1][j] == 'X':
                        uf.union(flat(i, j), flat(i+1, j))
        return uf.count