|
| 1 | +classSolution { |
| 2 | +publicvoidsolve(char[][]board) { |
| 3 | +intnRows =board.length; |
| 4 | +intnCols =board[0].length; |
| 5 | + |
| 6 | +// 1a) Capture unsurrounded regions - top and bottom row (O -> T) |
| 7 | +for (inti =0;i <nCols;i++) { |
| 8 | +if (board[0][i] =='O')dfs(board,0,i); |
| 9 | +if (board[nRows-1][i] =='O')dfs(board,nRows-1,i); |
| 10 | + } |
| 11 | + |
| 12 | +// 1b) Capture unsurrounded regions - Left and right columns (O -> T) |
| 13 | +for (inti =0;i <nRows;i++) { |
| 14 | +if (board[i][0] =='O')dfs(board,i,0); |
| 15 | +if (board[i][nCols-1] =='O')dfs(board,i,nCols-1); |
| 16 | + } |
| 17 | + |
| 18 | +for (intr =0;r <nRows;r++) { |
| 19 | +for (intc =0;c <nCols;c++) { |
| 20 | +if (board[r][c] =='O')board[r][c] ='X';// 2) Capture surrounded regions (O -> X) |
| 21 | +if (board[r][c] =='T')board[r][c] ='O';// 3) Uncapture unsurrounded regions (T- O) |
| 22 | + } |
| 23 | + } |
| 24 | + } |
| 25 | + |
| 26 | +privatevoiddfs(char[][]board,intr,intc) { |
| 27 | +intnRows =board.length; |
| 28 | +intnCols =board[0].length; |
| 29 | +if (r <0 ||c <0 ||r >=nRows ||c >=nCols ||board[r][c] !='O')return; |
| 30 | + |
| 31 | +board[r][c] ='T'; |
| 32 | +dfs(board,r+1,c); |
| 33 | +dfs(board,r-1,c); |
| 34 | +dfs(board,r,c+1); |
| 35 | +dfs(board,r,c-1); |
| 36 | + } |
| 37 | +} |