先标记，再清楚，类似jvm里面的可达性分析
class Solution {
int[] rowArray = {-1, 0, 1, 0};
int[] colArray = {0, 1, 0, -1};
int rowGlobal=0;
int colGlobal = 0;
public void solve(char[][] board) {
if(null==board || board.length==0){
return;
}
rowGlobal = board.length;
colGlobal = board[0].length;
boolean[][] flag = new boolean[rowGlobal][colGlobal];
for(int i = 0; i < rowGlobal; i++) {
for(int j = 0; j < colGlobal; j++){
if(i==0 || j==0 || (i==rowGlobal-1) || (j==colGlobal-1)){
markLabel(board,flag,i,j);
}
}
}
for(int i = 0; i < rowGlobal; i++){
for(int j = 0; j < colGlobal; j++){
if(!flag[i][j]&& board[i][j]=='O'){
board[i][j] = 'X';
}
}
}
}
void markLabel(char[][] board, boolean[][] flag, int row, int col){
// System.out.println(row+","+col);
if(board[row][col]=='X' || flag[row][col]){
return ;
}
// System.out.println(" "+row+","+col);
flag[row][col]=true;
for(int i = 0; i < 4; i++){
int nextRow = row+rowArray[i];
int nextCol = col+colArray[i];
// System.out.println(" "+nextRow+","+nextCol);
if(nextRow>=0 && nextRow<rowGlobal&& nextCol>=0 && nextCol<colGlobal){
// System.out.println(" "+nextRow+","+nextCol);
markLabel(board, flag, nextRow, nextCol);
}
}
}
}
网友评论