题目：
给你一个 M×N 的二维矩阵，其中包含字符 X 和 O，让你找到矩阵中四面被 X 围住的 O，并且把它们替换成 X。
注意哦，必须是四面被围的 O 才能被换成 X，也就是说边角上的 O 一定不会被围，进一步，与边角上的 O 相连的 O 也不会被 X 围四面，也不会被替换。
思路1：
DFS
先遍历四条边，找出O，并对O节点进行深度遍历，将相邻的O节点都设为#
然后遍历所有节点，将O设为X，将#设为O
class Solution {
public:
void solve(vector<vector<char>>& board) {
int m=board.size();
int n=board[0].size();
for(int i=0;i<m;++i){
if(board[i][0]=='O'){
traverse(board,i,0);
}
if(board[i][n-1]=='O'){
traverse(board,i,n-1);
}
}
for(int j=0;j<n;++j){
if(board[0][j]=='O'){
traverse(board,0,j);
}
if(board[m-1][j]=='O'){
traverse(board,m-1,j);
}
}
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
if(board[i][j]=='O'){
board[i][j]='X';
}
if(board[i][j]=='#'){
board[i][j]='O';
}
}
}
}
void traverse(vector<vector<char>>& board, int m,int n){
board[m][n]='#';
for(int i=0;i<4;++i){
int v=m+d[i][0];
int w=n+d[i][1];
if(v>=0&&v<board.size()&&w>=0&&w<board[0].size()){
if(board[v][w]=='O'){
traverse(board,v,w);
}
}
}
}
int d[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
};
思路2：
你可以把那些不需要被替换的O看成一个拥有独门绝技的门派，它们有一个共同祖师爷叫dummy，这些O和dummy互相连通，而那些需要被替换的O与dummy不连通。
首先要解决的是，根据我们的实现，Union-Find 底层用的是一维数组，构造函数需要传入这个数组的大小，而题目给的是一个二维棋盘。
这个很简单，二维坐标(x,y)可以转换成x * n + y这个数（m是棋盘的行数，n是棋盘的列数）。敲黑板，这是将二维坐标映射到一维的常用技巧。
其次，我们之前描述的「祖师爷」是虚构的，需要给他老人家留个位置。索引[0.. m*n-1]都是棋盘内坐标的一维映射，那就让这个虚拟的dummy节点占据索引m*n好了。
class UF{
public:
UF(int n){
count=n;
for(int i=0;i<n;++i){
parent.push_back(i);
size.push_back(1);
}
}
//p和q连通
void Union(int p,int q){
int rootp=find(p);
int rootq=find(q);
if(rootq==rootp)
return;
//小树接到大树下边，比较平均
if(size[rootp]>size[rootq]){
size[rootq]+=size[rootp];
parent[rootp]=rootq;
}else{
size[rootp]+=size[rootq];
parent[rootq]=rootp;
}
count--;
}
/* 返回节点 x 的根节点 */
int find(int x){
while(x!=parent[x]){
// 进行路径压缩
parent[x]=parent[parent[x]];
x=parent[x];
}
return x;
}
/* 判断 p 和 q 是否互相连通 */
bool connected(int p,int q){
int rootp=find(p);
int rootq=find(q);
// 处于同一棵树上的节点，相互连通
return rootp==rootq;
}
//记录连通分量个数
int count;
//存储若干棵树
vector<int> parent;
//记录树的重量
vector<int> size;
};
class Solution {
public:
void solve(vector<vector<char>>& board) {
int m=board.size();
int n=board[0].size();
// 给 dummy 留一个额外位置
UF uf(m*n+1);
int dummy=m*n;
// 将首列和末列的 O 与 dummy 连通
for(int i=0;i<m;++i){
if(board[i][0]=='O'){
uf.Union(i*n,dummy);
}
if(board[i][n-1]=='O'){
uf.Union(i*n+n-1,dummy);
}
}
// 将首行和末行的 O 与 dummy 连通
for(int j=0;j<n;++j){
if(board[0][j]=='O'){
uf.Union(j,dummy);
}
if(board[m-1][j]=='O'){
uf.Union((m-1)*n+j,dummy);
}
}
for(int i=1;i<m-1;++i){
for(int j=1;j<n-1;++j){
if(board[i][j]=='O'){
// 将此 O 与上下左右的 O 连通
for(int k=0;k<4;++k){
int v=i+d[k][0];
int w=j+d[k][1];
if(board[v][w]=='O'){
uf.Union(v*n+w,i*n+j);
}
}
}
}
}
// 所有不和 dummy 连通的 O，都要被替换
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
if(board[i][j]=='O'){
if(!uf.connected(i*n+j,dummy)){
board[i][j]='X';
}
}
}
}
}
// 方向数组 d 是上下左右搜索的常用手法
int d[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
};