首页 > 代码库 > [LeetCode] Surrounded Regions（DFS、BFS）
[LeetCode] Surrounded Regions（DFS、BFS）
Given a 2D board containing ‘X‘ and ‘O‘, capture all regions surrounded by ‘X‘.
A region is captured by flipping all ‘O‘s into ‘X‘s in that surrounded region.
For 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
方法1：DFS的Recursive实现，由于递归实现占用额外内存，当递归深度大时出现RunTime Error
思想是从board的外层四周开始，找到需要替换的‘O’先标记为‘V’，看此‘O’上下左右有没有需要替换的‘O’，不断深入。
class Solution { public: typedef vector<vector<char> > BOARDTYPE; void solve(BOARDTYPE &board) { if (board.empty() || board[0].empty()) return; int N = board.size(), M = board[0].size(); for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) if (i == 0 || j == 0 || i == N-1 || j == M-1) dfs(board, i, j); // you may call dfs or bfs here! for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) board[i][j] = (board[i][j] == ‘V‘) ? ‘O‘ : ‘X‘; } void dfs(BOARDTYPE &board, int row, int col) { int N = board.size(), M = board[0].size(); if (row < 0 || row >= N || col < 0 || col >= M) return; if (board[row][col] != ‘O‘) return; board[row][col] = ‘V‘;//把不需要更改的‘O’设为‘V’. dfs(board, row+1, col); dfs(board, row-1, col); dfs(board, row, col+1); dfs(board, row, col-1); } };
方法2：DFS的stack实现
It pushes all neighbors into stack, and pick the top one, which is one of the neighbors just pushed in, and further gets its neighbors.
仔细考虑一下，这个乍一看很容易被认为是BFS的实现。
class Solution { public: typedef vector<vector<char> > BOARDTYPE; void solve(BOARDTYPE &board) { if (board.empty() || board[0].empty()) return; int N = board.size(), M = board[0].size(); for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) if (i == 0 || j == 0 || i == N-1 || j == M-1) dfs(board, i, j); // you may call dfs or bfs here! for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) board[i][j] = (board[i][j] == ‘V‘) ? ‘O‘ : ‘X‘; } void dfs(BOARDTYPE &board, int row, int col) { int N = board.size(), M = board[0].size(); if (row < 0 || row >= N || col < 0 || col >= M) return; if (board[row][col] != ‘O‘) return; stack<pair<int,int>> s; s.push(make_pair(row,col)); board[row][col] = ‘V‘;//把不需要更改的‘O’设为‘V’. while(!s.empty()){ row = s.top().first; col = s.top().second; s.pop(); if(row+1<N && board[row+1][col]==‘O‘){ s.push(make_pair(row+1,col)); board[row+1][col]=‘V‘; } if(row-1>=0 && board[row-1][col]==‘O‘){ s.push(make_pair(row-1,col)); board[row-1][col]=‘V‘; } if(col+1<M && board[row][col+1]==‘O‘){ s.push(make_pair(row,col+1)); board[row][col+1]=‘V‘; } if(col-1<N && board[row][col-1]==‘O‘){ s.push(make_pair(row,col-1)); board[row][col-1]=‘V‘; } }//end while } };
方法3：BFS的queue实现
class Solution { public: typedef vector<vector<char> > BOARDTYPE; void solve(BOARDTYPE &board) { if (board.empty() || board[0].empty()) return; int N = board.size(), M = board[0].size(); queue<pair<int,int>> q; for (int i = 0; i < N; ++i){ if(board[i][M-1]==‘O‘ ){ q.push(make_pair(i,M-1)); board[i][M-1]=‘V‘; } if(board[i][0]==‘O‘){ q.push(make_pair(i,0)); board[i][0]=‘V‘; } } for (int j = 0; j < M; ++j){ if(board[0][j]==‘O‘){ q.push(make_pair(0,j)); board[0][j]=‘V‘; } if( board[N-1][j]==‘O‘){ q.push(make_pair(N-1,j)); board[N-1][j]=‘V‘; } } bfs(board,q); for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) board[i][j] = (board[i][j] == ‘V‘) ? ‘O‘ : ‘X‘; } void bfs(BOARDTYPE &board, queue<pair<int,int>> &q) { int N = board.size(), M = board[0].size(); while(!q.empty()){ int row = q.front().first; int col = q.front().second; q.pop(); if(row+1<N && board[row+1][col]==‘O‘){ q.push(make_pair(row+1,col)); board[row+1][col]=‘V‘; } if(row-1>=0 && board[row-1][col]==‘O‘){ q.push(make_pair(row-1,col)); board[row-1][col]=‘V‘; } if(col+1<M && board[row][col+1]==‘O‘){ q.push(make_pair(row,col+1)); board[row][col+1]=‘V‘; } if(col-1<N && board[row][col-1]==‘O‘){ q.push(make_pair(row,col-1)); board[row][col-1]=‘V‘; } }//end while } };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。