LeetCode-130. Surrounded Regions

LeetCode-130. Surrounded Regions

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 XX O O XX X O XX O X X

After running your function, the board should be:

X X X XX X X XX X X XX 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.

题解：

之前dfs效率很低，看别人思路：

只有边上为O往内延伸的所有为O路径才是不会被围着的，直接搜四边并标记路径即可。

class Solution {public: void bfs(vector>& board, int x, int y, int n, int m) { if (x >= 0 && x < n && y >= 0 && y < m) { if (board[x][y] == 'O') { board[x][y] = 'Y'; bfs(board, x + 1, y, n, m); bfs(board, x - 1, y, n, m); bfs(board, x, y + 1, n, m); bfs(board, x, y - 1, n, m); } } } void solve(vector>& board) { if (board.empty() == true) { return; } int n = board.size(), m = board[0].size(); for (int i = 0; i < n; i++) { if (board[i][0] == 'O') { bfs(board, i, 0, n, m); } if (board[i][m - 1] == 'O') { bfs(board, i, m - 1, n, m); } } for (int j = 0; j < m; j++) { if (board[0][j] == 'O') { bfs(board, 0, j, n, m); } if (board[n - 1][j] == 'O') { bfs(board, n - 1, j, n, m); } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (board[i][j] == 'Y') { board[i][j] = 'O'; } else { board[i][j] = 'X'; } } } }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。