Sponsored
Sponsored
This approach uses Depth-First Search (DFS) to mark all 'O's connected to the boundary as safe. These 'O's cannot be converted to 'X' because they are on the boundary or connected to the boundary. The rest of the 'O's can be safely converted to 'X'.
Time Complexity: O(m * n), Space Complexity: O(m * n) due to the DFS recursion stack.
1#include <stdio.h>
2
3void dfs(char** board, int row, int col, int m, int n) {
4 if (row < 0 || col < 0 || row >= m || col >= n || board[row][col] != 'O') {
5 return;
6 }
7 board[row][col] = 'A';
8 dfs(board, row - 1, col, m, n);
9 dfs(board, row + 1, col, m, n);
10 dfs(board, row, col - 1, m, n);
11 dfs(board, row, col + 1, m, n);
12}
13
14void solve(char** board, int boardSize, int* boardColSize) {
15 int m = boardSize;
16 int n = boardColSize[0];
17 if (m == 0) return;
18
19 for (int i = 0; i < m; i++) {
20 if (board[i][0] == 'O') dfs(board, i, 0, m, n);
21 if (board[i][n - 1] == 'O') dfs(board, i, n - 1, m, n);
22 }
23 for (int j = 0; j < n; j++) {
24 if (board[0][j] == 'O') dfs(board, 0, j, m, n);
25 if (board[m - 1][j] == 'O') dfs(board, m - 1, j, m, n);
26 }
27 for (int i = 0; i < m; i++) {
28 for (int j = 0; j < n; j++) {
29 if (board[i][j] == 'O') board[i][j] = 'X';
30 if (board[i][j] == 'A') board[i][j] = 'O';
31 }
32 }
33}In this C implementation, we perform a DFS from each 'O' on the boundary, marking connected 'O's as 'A'. After marking, we iterate the board again to flip all 'O's to 'X' and revert 'A' back to 'O'.
This approach uses Breadth-First Search (BFS) utilizing a queue to explore 'O's connected to the boundary. This approach is iterative and avoids deep recursion, keeping the method stack usage low.
Time Complexity: O(m * n), Space Complexity: O(m * n) for the queue's maximal use.
1import java
Using BFS with a queue in Java, border-connected 'O's are marked, securing them from conversion to 'X'. This iterative method handles potential issue with recursion depth.