130.被围绕的区域

一、问题描述

被围绕的区域：给定一个二维数组 board，其中包含 'X' 和 'O'。我们需要将所有被 'X' 围绕的区域中的 'O' 替换为 'X'。被围绕的区域的定义是，这个区域的所有 'O' 都被 'X' 包围，也就是说，这个区域不与边界上的 'O' 相连。边界上的 'O' 不被看作被围绕的。

二、方案一：使用深度优先搜索

1、思路

• 遍历边界上的所有单元格。如果遇到 'O'，则使用 DFS 将所有与边界相连的 'O' 标记为 'A'。
• 再次遍历整个矩阵，将所有未被标记的 'O'（即被 'X' 围绕的 'O'）替换为 'X'。
• 最后，将所有 'A' 恢复为 'O'。

2、代码实现

func solve(board [][]byte) {
    if len(board) == 0 {
        return // 如果矩阵为空，直接返回
    }

    n, m := len(board), len(board[0]) // n 和 m 分别是矩阵的行数和列数

    // 遍历矩阵的边界，将边界上的 'O' 以及与边界 'O' 相连的 'O' 标记为 'A'
    // 如果我们只从 `(0, 0)` 开始 DFS，那么只有那些与 `(0, 0)` 直接或间接相连的 `'O'` 会被标记，而位于矩阵其他区域的 `'O'` 可能不会被访问到
    // 从矩阵的每个边界点开始 DFS，这样才能正确地标记所有与边界相连的 `'O'`
    for i := 0; i < n; i++ {
        dfs(board, i, 0)     // 遍历左边界
        dfs(board, i, m-1)   // 遍历右边界
    }
    for j := 1; j < m-1; j++ {
        dfs(board, 0, j)     // 遍历上边界
        dfs(board, n-1, j)   // 遍历下边界
    }

    // 再次遍历矩阵，将未被标记的 'O' 替换为 'X'
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if board[i][j] == 'O' {
                board[i][j] = 'X' // 将被围绕的 'O' 替换为 'X'
            } else if board[i][j] == 'A' {
                board[i][j] = 'O' // 将标记的 'A' 恢复为 'O'
            }
        }
    }
}

// 深度优先搜索函数，用于将边界上的 'O' 以及与边界 'O' 相连的 'O' 标记为 'A'
func dfs(board [][]byte, i, j int) {
    n, m := len(board), len(board[0])
    if i < 0 || i >= n || j < 0 || j >= m || board[i][j] != 'O' {
        return // 如果索引越界或当前位置不是 'O'，则返回
    }
    board[i][j] = 'A' // 将当前位置标记为 'A'
    // 递归搜索上下左右四个方向
    dfs(board, i+1, j)
    dfs(board, i-1, j)
    dfs(board, i, j+1)
    dfs(board, i, j-1)
}

3、复杂度分析

• 时间复杂度：O(n*m)，其中 n 和 m 分别是矩阵的行数和列数。在最坏的情况下，我们可能需要遍历整个矩阵多次。
• 空间复杂度：O(n*m)，这是递归调用栈的空间复杂度。

三、方案二：使用并查集

1、思路

• 创建一个并查集，其大小为 n * m，用于处理所有单元格。
• 遍历矩阵的边界，将所有边界上的 'O' 以及与边界 'O' 相连的 'O' 合并到同一个集合中。
• 再次遍历整个矩阵，将所有不属于这些集合的 'O' 替换为 'X'。

2、代码实现

type UnionFind struct {
	parent []int // 用于存储每个元素的父节点，即它所在集合的代表元素或根节点
	rank   []int // 树的高度
	count  int   // 并查集中剩余的集合数量
}

// 创建并查集的构造函数
func NewUnionFind(n int) *UnionFind {
	parent := make([]int, n)
	rank := make([]int, n)
	for i := range parent {
		parent[i] = i
		rank[i] = 1
	}
	return &UnionFind{parent, rank, n}
}

// 查找元素的根节点，同时进行路径压缩
func (uf *UnionFind) Find(x int) int {
	if uf.parent[x] != x {
		uf.parent[x] = uf.Find(uf.parent[x])
	}
	return uf.parent[x]
}

// 合并两个元素所在的集合
func (uf *UnionFind) Union(x, y int) {
	rootX, rootY := uf.Find(x), uf.Find(y)
	if rootX != rootY {
		if uf.rank[rootX] > uf.rank[rootY] {
			uf.parent[rootY] = rootX
		} else if uf.rank[rootX] < uf.rank[rootY] {
			uf.parent[rootX] = rootY
		} else {
			uf.parent[rootY] = rootX
			uf.rank[rootX]++
		}
		// 每次执行“合并”操作时，集合的数量就会减少
		uf.count--
	}
}

func solve(board [][]byte) {
	if len(board) == 0 {
		return
	}

	n, m := len(board), len(board[0])
	uf := NewUnionFind(n*m + 1)
	// 虚拟节点，用于连接所有边界上的 'O'
	dummy := n * m

	// 遍历矩阵，将边界上的 'O' 和与之相连的 'O' 合并到虚拟节点
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if board[i][j] == 'O' {
				// 边界上的 'O' 不会被包围，都合并到同一个集合中
				if i == 0 || i == n-1 || j == 0 || j == m-1 {
					uf.Union(i*m+j, dummy)
				} else {
					// 将当前 'O' 与其上下左右的 'O' 合并
					if i > 0 && board[i-1][j] == 'O' {
						uf.Union(i*m+j, (i-1)*m+j)
					}
					if i < n-1 && board[i+1][j] == 'O' {
						uf.Union(i*m+j, (i+1)*m+j)
					}
					if j > 0 && board[i][j-1] == 'O' {
						uf.Union(i*m+j, i*m+(j-1))
					}
					if j < m-1 && board[i][j+1] == 'O' {
						uf.Union(i*m+j, i*m+(j+1))
					}
				}
			}
		}
	}

	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if board[i][j] == 'O' && uf.Find(i*m+j) != uf.Find(dummy) {
				board[i][j] = 'X'
			}
		}
	}
}

3、复杂度分析

• 时间复杂度：O(nmα(nm))，其中 α 是阿克曼函数的反函数，用于表示并查集操作的平均时间复杂度。在最坏的情况下，α(nm) 接近于 O(1)，所以整个算法的时间复杂度接近于 O(n*m)。
• 空间复杂度：O(n*m)，用于存储并查集的数据结构。

四、总结

方案	时间复杂度	空间复杂度	优点	缺点
DFS	O(n*m)	O(n*m)	实现简单，易于理解	可能需要多次遍历整个矩阵
Union-Find	O(nmα(nm)) ≈ O(nm)	O(n*m)	高效，特别是对于大数据集	实现复杂，需要理解并查集

在实际应用中，选择哪种方案取决于具体的需求和数据规模。对于小规模或中等规模的问题，方案一通常更易于实现和理解。而对于大规模问题，方案二的高效率可能更受欢迎。