Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
Example:
X X X X X O O X X X O X X O X X
After running your function, the board should be:
X X X X X X X X X X X X X O X X
Explanation:
Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.
Solution: DFS
Time complexity: O(m*n)
Space complexity: O(m*n)
Only starts DFS at border cells of O.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// Author: Huahua class Solution { public: void solve(vector<vector<char>>& board) { const int m = board.size(); if (m == 0) return; const int n = board[0].size(); function<void(int, int)> dfs = [&](int x, int y) { if (x < 0 || x >= n || y < 0 || y >= m || board[y][x] != 'O') return; board[y][x] = 'G'; // mark it as good dfs(x - 1, y); dfs(x + 1, y); dfs(x, y - 1); dfs(x, y + 1); }; for (int y = 0; y < m; ++y) dfs(0, y), dfs(n - 1, y); for (int x = 0; x < n; ++x) dfs(x, 0), dfs(x, m - 1); map<char, char> v{{'G','O'},{'O','X'}, {'X','X'}}; for (int y = 0; y < m; ++y) for (int x = 0; x < n; ++x) board[y][x] = v[board[y][x]]; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment