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 <vector>
2using namespace std;
3
4void dfs(vector<vector<char>>& board, int row, int col, int m, int n) {
5 if (row < 0 || col < 0 || row >= m || col >= n || board[row][col] != 'O') return;
6 board[row][col] = 'A';
7 dfs(board, row - 1, col, m, n);
8 dfs(board, row + 1, col, m, n);
9 dfs(board, row, col - 1, m, n);
10 dfs(board, row, col + 1, m, n);
11}
12
13void solve(vector<vector<char>>& board) {
14 int m = board.size();
15 if (m == 0) return;
16 int n = board[0].size();
17
18 for (int i = 0; i < m; ++i) {
19 if (board[i][0] == 'O') dfs(board, i, 0, m, n);
20 if (board[i][n - 1] == 'O') dfs(board, i, n - 1, m, n);
21 }
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
28 for (int i = 0; i < m; ++i) {
29 for (int j = 0; j < n; ++j) {
30 if (board[i][j] == 'O') board[i][j] = 'X';
31 if (board[i][j] == 'A') board[i][j] = 'O';
32 }
33 }
34}This C++ implementation uses DFS to mark safe 'O's with 'A' and converts the rest to 'X', similar to the C implementation. This is efficient in terms of time and space, especially for a constrained matrix.
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.
1#include
In this C implementation using BFS, a queue holds nodes to explore. Marking 'O's as 'A' when connected to border starts from queues, flipping others to 'X'.