[leetcode刷题系列]Surrounded Regions

本文主要是介绍[leetcode刷题系列]Surrounded Regions，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

囧， 这题用dfs我re了，应该是爆栈了。 于是改成了bfs就过了

const int MAXN = 1000 + 10;const int dx[] = {-1, 0, 0, 1};
const int dy[] = {0, -1, 1, 0};int n, m;
bool vis[MAXN][MAXN];void bfs(int r, int c, vector<vector<char> > & board){queue<pair<int, int> > q;q.push(make_pair(r, c));vis[r][c] = 1;while(!q.empty()){r = q.front().first;c = q.front().second;q.pop();for(int p = 0; p < 4; ++ p){int nr = r + dx[p];int nc = c + dy[p];if(nr >= 0 && nr < n)if(nc >= 0 && nc < m)if(!vis[nr][nc])if(board[nr][nc] == 'O'){vis[nr][nc] = 1;q.push(make_pair(nr, nc));}}}
}
class Solution {
public:void solve(vector<vector<char>> &board) {// Start typing your C/C++ solution below// DO NOT write int main() functionif(board.size() <= 0 || board[0].size() <= 0)return;memset(vis, 0x00, sizeof(vis));n = board.size();m = board[0].size();for(int i = 0; i < m; ++ i)if(board[0][i] == 'O')if(!vis[0][i])bfs(0, i, board);for(int i = 0; i< m; ++ i)if(board[n - 1][i] == 'O')if(!vis[n - 1][i])bfs(n - 1, i, board);for(int i = 0; i < n; ++ i)if(board[i][0] == 'O')if(!vis[i][0])bfs(i, 0, board);for(int i = 0; i < n; ++ i)if(board[i][m - 1] == 'O')if(!vis[i][m - 1])bfs(i, m - 1, board);for(int i = 0; i < n; ++ i)for(int j = 0; j < m; ++ j)if(board[i][j] == 'O')if(!vis[i][j])board[i][j] = 'X';}
};

这篇关于[leetcode刷题系列]Surrounded Regions的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---