题目
Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.
A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.
For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
思路:使用并查集 将相邻且符号相同的元素放到通一个集合中,维护处于边缘的节点,因为只有一个”O”的集合中存在一个元素在矩阵的边缘时,这个集合才不会被”X”包围,所以需要一个维护节点是否在边缘(或者集合中的代表元素表示集合中是否存在一个在边缘的几点).
代码:
class Solution {private int[] s;private boolean[] isedge;public void solve(char[][] board) {if(board == null || board.length == 0)return;int clen = board[0].length;int length = board.length*clen;s = new int[length];isedge = new boolean[length];//初始化边缘节点 使其为真for(int i=0;i<length;i++){s[i] = i;int x = i/clen;int y = i%clen;if( board[x][y] == 'O' && (x == 0 || x == board.length-1 || y == 0 || y == clen-1) ){isedge[i] = true;}}//相邻且符号相同的元素合并for(int i=0;i<length;i++){int x = i/clen;int y = i%clen;int down = x+1,right = y+1;//只需判断其 右方和下方的元素即可if(down<board.length && board[down][y] == board[x][y]){merge(i,i+clen);}if(right<clen && board[x][right] == board[x][y]){merge(i,i+1);}}//将没有边缘节点的"O"集合转为"X"for(int i=0;i<length;i++){int x = i/clen;int y = i%clen;if(board[x][y] == 'O' && !isedge[find(i)]){board[x][y] = 'X';}}}public void merge(int a,int b){int af = find(a);int bf = find(b);if(af == bf ){return;}//合并过程中 将边缘节点的 边缘特性赋予给其代表节点s[bf] = af;if(isedge[bf]){isedge[af] = true;}}public int find(int c){if(c!=s[c]){s[c] = find(s[c]);}return s[c];}
}