| 1 | class Solution { |
| 2 | |
| 3 | public void solve(char[][] board) { |
| 4 | int nRows = board.length; |
| 5 | int nCols = board[0].length; |
| 6 | |
| 7 | // 1a) Capture unsurrounded regions - top and bottom row (O -> T) |
| 8 | for (int i = 0; i < nCols; i++) { |
| 9 | if (board[0][i] == 'O') dfs(board, 0, i); |
| 10 | if (board[nRows - 1][i] == 'O') dfs(board, nRows - 1, i); |
| 11 | } |
| 12 | |
| 13 | // 1b) Capture unsurrounded regions - Left and right columns (O -> T) |
| 14 | for (int i = 0; i < nRows; i++) { |
| 15 | if (board[i][0] == 'O') dfs(board, i, 0); |
| 16 | if (board[i][nCols - 1] == 'O') dfs(board, i, nCols - 1); |
| 17 | } |
| 18 | |
| 19 | for (int r = 0; r < nRows; r++) { |
| 20 | for (int c = 0; c < nCols; c++) { |
| 21 | if (board[r][c] == 'O') board[r][c] = 'X'; // 2) Capture surrounded regions (O -> X) |
| 22 | if (board[r][c] == 'T') board[r][c] = 'O'; // 3) Uncapture unsurrounded regions (T- O) |
| 23 | } |
| 24 | } |
| 25 | } |
| 26 | |
| 27 | private void dfs(char[][] board, int r, int c) { |
| 28 | int nRows = board.length; |