📑 题目：130. 被围绕的区域

🚀 本题 LeetCode 传送门

题目大意

给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

解题思路

  • 给出一张二维地图，要求把地图上非边缘上的 ‘O’ 都用 ‘X’ 覆盖掉。
  • 这一题有多种解法。第一种解法是并查集。先将边缘上的 ‘O’ 全部都和一个特殊的点进行 union() 。然后再把地图中间的 ‘O’ 都进行 union()，最后把和特殊点不是同一个集合的点都标记成 ‘X’。第二种解法是 DFS 或者 BFS，可以先将边缘上的 ‘O’ 先标记成另外一个字符，然后在递归遍历过程中，把剩下的 ‘O’ 都标记成 ‘X’。

代码

  1. package leetcode
  3. import (
  4.  "github.com/halfrost/LeetCode-Go/template"
  5. )
  7. // 解法一 并查集
  8. func solve(board [][]byte) {
  9.  if len(board) == 0 {
  10.   return
  11.  }
  12.  m, n := len(board[0]), len(board)
  13.  uf := template.UnionFind{}
  14.  uf.Init(n*m + 1) // 特意多一个特殊点用来标记
  16.  for i := 0; i < n; i++ {
  17.   for j := 0; j < m; j++ {
  18.    if (i == 0 || i == n-1 || j == 0 || j == m-1) && board[i][j] == 'O' { //棋盘边缘上的 'O' 点
  19.     uf.Union(i*m+j, n*m)
  20.    } else if board[i][j] == 'O' { //棋盘非边缘上的内部的 'O' 点
  21.     if board[i-1][j] == 'O' {
  22.      uf.Union(i*m+j, (i-1)*m+j)
  23.     }
  24.     if board[i+1][j] == 'O' {
  25.      uf.Union(i*m+j, (i+1)*m+j)
  26.     }
  27.     if board[i][j-1] == 'O' {
  28.      uf.Union(i*m+j, i*m+j-1)
  29.     }
  30.     if board[i][j+1] == 'O' {
  31.      uf.Union(i*m+j, i*m+j+1)
  32.     }
  34.    }
  35.   }
  36.  }
  37.  for i := 0; i < n; i++ {
  38.   for j := 0; j < m; j++ {
  39.    if uf.Find(i*m+j) != uf.Find(n*m) {
  40.     board[i][j] = 'X'
  41.    }
  42.   }
  43.  }
  44. }
  46. // 解法二 DFS
  47. func solve1(board [][]byte) {
  48.  for i := range board {
  49.   for j := range board[i] {
  50.    if i == 0 || i == len(board)-1 || j == 0 || j == len(board[i])-1 {
  51.     if board[i][j] == 'O' {
  52.      dfs130(i, j, board)
  53.     }
  54.    }
  55.   }
  56.  }
  58.  for i := range board {
  59.   for j := range board[i] {
  60.    if board[i][j] == '*' {
  61.     board[i][j] = 'O'
  62.    } else if board[i][j] == 'O' {
  63.     board[i][j] = 'X'
  64.    }
  65.   }
  66.  }
  67. }
  69. func dfs130(i, j int, board [][]byte) {
  70.  if i < 0 || i > len(board)-1 || j < 0 || j > len(board[i])-1 {
  71.   return
  72.  }
  73.  if board[i][j] == 'O' {
  74.   board[i][j] = '*'
  75.   for k := 0; k < 4; k++ {
  76.    dfs130(i+dir[k][0], j+dir[k][1], board)
  77.   }
  78.  }
  79. }