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
#并查集实现略
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