7-31算法，被围绕的区域（一）

题目描述

给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。

找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

示例:

X X X X
X O O X
X X O X
X O X X

运行你的函数后，矩阵变为：

X X X X
X X X X
X X X X
X O X X

解释:

被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

思路

此题可以使用并查集，首先进行遍历，将所有相邻的’O’归于一个集合里面，同时，将边界上的’O’与一个虚拟的节点归为一个集合以作区分。然后，再次遍历，将所有既是’O’又不和那个虚拟节点一个集合的元素改成’X’输出。

代码

class Union{
	vector<int> pre;
public:
	Union(n){
		pre.resize(n);
		for(int i=0; i<n; i++)
			pre[i] = i;
	}
	int search(int root){
		int son, temp;
		son = root;
		while(root != pre[root])
			root = pre[root];
		while(son != root){
			temp = pre[son];
			pre[son] = root;
			son = temp;
		}
		return root;
	}
	void join(int x, int y){
		int root1 = search(x);
		int root2 = search(y);
		if(root1 != root2)
			pre[root2] = root1;
	}
	boolean isConnect(int node1, int node2){
		return search(node1) == search(node2);
	}
};
class Solution {
public:
	void solve(vector<vector<char>>& board) {
		if(board.size() == 0)//注意要考虑数组为空的情况
			return;
		int row,col;
		row = board.size();
		col = board[0].size();
		dsu set = dsu(row*col+1);
		for(int i=0; i<row; i++)
			for(int j=0; j<col; j++){
				if(board[i][j] == 'O'){
					if(i==0||j==0||i==row-1||j==col-1){
						set.join(row*col, node(i,j,col));
					}else{
						if(board[i-1][j] == 'O')
							set.join(node(i-1,j,col), node(i,j,col));
						if(board[i+1][j] == 'O')
							set.join(node(i+1,j,col), node(i,j,col));
						if(board[i][j-1] == 'O')
							set.join(node(i,j-1,col), node(i,j,col));
						if(board[i][j+1] == 'O')
							set.join(node(i,j+1,col), node(i,j,col));
					}
				}
			}
		for(int i=0; i<row; i++){
			for(int j=0; j<col; j++){
				if(board[i][j] == 'O'&&set.isConnect(node(i,j,col),row*col)!=1)
					board[i][j] = 'X';
				}
		}
	}
	int node(int i, int j, int col){
		return j+i*col;
	}
};