题目：

  1. 给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
  3. 找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
  5. 示例:
  7. X X X X
  8. X O O X
  9. X X O X
  10. X O X X
  11. 运行你的函数后，矩阵变为：
  13. X X X X
  14. X X X X
  15. X X X X
  16. X O X X
  18. 来源：力扣（LeetCode）
  19. 链接：https://leetcode-cn.com/problems/surrounded-regions
  20. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

答案：

时间：

15min，pos算错了

  1. class UnionFind:
  2.     def __init__(self,n):
  3.         self.parent = [i for i in range(n)]
  4.         self.rank = [1 for _ in range(n)]
  5.         self.rank[-1]=float("inf")
  6.         self.count = n
  8.     def find(self,p):
  9.         while self.parent[p] != self.parent[self.parent[p]]:
  10.             self.parent[p] = self.parent[self.parent[p]]
  11.         return self.parent[p]
  13.     def union(self,p,q):
  14.         i = self.find(p)
  15.         j = self.find(q)
  16.         if i == j:
  17.             return
  18.         if self.rank [i] < self.rank [j]:
  19.             self.parent[i] = j
  20.             self.rank [j] += self.rank [i]
  21.         else:
  22.             self.parent[j] = i
  23.             self.rank [i] += self.rank [j]
  24.         self.count -= 1
  26. class Solution:
  27.     def solve(self, board: List[List[str]]) -> None:
  28.         """
  29.         Do not return anything, modify board in-place instead.
  30.         """
  31.         if not board or not board[0]:return
  32.         m,n=len(board),len(board[0])
  33.         area=UnionFind(m*n+1)
  34.         directs=[(1,0),(-1,0),(0,1),(0,-1)]
  36.         for i in range(m):
  37.             for j in range(n):
  38.                 pos=i*n+j
  39.                 if board[i][j]=="X":area.union(pos,m*n)
  40.                 else:
  41.                     if i==0 or j==0 or j==n-1 or i==m-1:area.union(pos,m*n)
  42.                     else:
  43.                         for ix,iy in directs:
  44.                             new_i,new_j=i+ix,j+iy
  45.                             new_pos=new_i*n+new_j
  46.                             if board[new_i][new_j]=="O":
  47.                                 area.union(pos,new_pos)
  49.         for i in range(m):
  50.             for j in range(n):
  51.                 pos=i*n+j
  52.                 if area.find(pos)!=m*n:
  53.                     board[i][j]="X"

要点：

1. 用并查集去想，边界肯定连到黑洞区域里（m*n+1），X连到黑洞里即可

那么为了让他们的爹同一，给于黑洞最大的rank，在并查集的地方做个小修改即可

  1. self.rank[-1]=float("inf")

2. 三个地方pos算错，太傻比了

pos=i*n+j，别搞错了

3. 找到不在黑洞里的填充就好了

其他：

代码报错：无