首页 > 代码库 > [LeetCode] Surrounded Regions
[LeetCode] Surrounded Regions
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
思路是从外围是’O‘的开始深度往里走，这时候里面的‘O‘就有两种命运，一种是跟外围的’O‘是联通的，那么这些‘O‘就可以存活，剩下的孤立的’O‘就没办法了，就只能被‘X‘了，为了区分这两种’O‘，我们把联通 的‘O‘改为另外一种统一而独立的字符，便于后期做恢复。这就是三步走（或两步）。
1）首先从外围的‘O‘处深度搜索，见到链接的’O‘就把他们都改为其他标识。
2）将剩余的孤立的’O‘改为‘X‘，同时，将遇到标识符改为’O‘。
简单吧，简单的一塌糊涂，但是这种思路太精髓了。
深度周游DFS
1 class Solution { 2 public: 3 void dfs(vector<vector<char> > &board, int i, int j) 4 { 5 size_t row = board.size(); 6 size_t col = board[0].size(); 7 8 if(i < 0 || i > row-1 || j < 0 || j > col-1) 9 return;10 if(board[i][j] != ‘O‘)11 return;12 board[i][j] = ‘*‘;//tag, in order to reverse back13 dfs(board, i, j-1);14 dfs(board, i, j+1);15 dfs(board, i-1, j);16 dfs(board, i+1, j);17 }18 19 void solve(vector<vector<char> > &board)20 {21 size_t row = board.size();22 size_t col = board[0].size();23 24 // dfs traverse form the up and down25 for(int j = 0; j < col; j++)26 { 27 dfs(board, 0 ,j);28 dfs(board,row-1, j); 29 } 30 31 // dfs traverse form the left and right 32 for(int i = 0; i < row; i++)33 { 34 dfs(board, i, 0); 35 dfs(board, i, col-1);36 }37 38 for(int i = 0; i < row; i++)39 {40 for(int j = 0; j < col; j++)41 {42 if(board[i][j] == ‘O‘)43 board[i][j] = ‘X‘;44 else if(board[i][j] == ‘*‘)45 board[i][j] = ‘O‘;46 }47 }48 49 50 }51 };
广度周游BFS
1 class Solution { 2 queue<pair<int, int> > m_que; 3 public: 4 void dfs(vector<vector<char> > &board, int i, int j) 5 { 6 size_t row = board.size(); 7 size_t col = board[0].size(); 8 9 if(i < 0 || i > row-1 || j < 0 || j > col-1)10 return;11 if(board[i][j] != ‘O‘)12 return;13 board[i][j] = ‘*‘;//tag, in order to reverse back14 dfs(board, i, j-1);15 dfs(board, i, j+1);16 dfs(board, i-1, j);17 dfs(board, i+1, j);18 }19 20 void fill(vector<vector<char> > &board, int x, int y){21 size_t row = board.size();22 size_t col = board[0].size();23 24 if(x<0 || x>=row || y<0 || y>=col || board[x][y]!=‘O‘)25 return;26 27 pair<int, int> p ;28 p.first = x;29 p.second = y;30 m_que.push(p);31 32 board[x][y]=‘*‘;33 }34 35 36 void bfs(vector<vector<char> > &board, int i, int j)37 {38 fill(board, i, j);39 40 while(!m_que.empty())41 {42 pair<int, int> p = m_que.front() ;43 m_que.pop();44 45 i = p.first;46 j = p.second;47 48 fill(board, i, j-1);49 fill(board, i, j+1);50 fill(board, i-1, j);51 fill(board, i+1, j);52 }53 54 }55 56 void solve(vector<vector<char> > &board)57 {58 if (board.empty()) return;59 size_t row = board.size();60 size_t col = board[0].size();61 62 // dfs traverse form the up and down63 for(int j = 0; j < col; j++)64 {65 #if 0 66 dfs(board, 0 ,j);67 dfs(board,row-1, j);68 #endif69 bfs(board, 0 ,j);70 bfs(board,row-1, j);71 72 }73 74 // dfs traverse form the left and right 75 for(int i = 0; i < row; i++)76 {77 #if 078 dfs(board, i, 0);79 dfs(board, i, col-1);80 #endif81 bfs(board, i, 0);82 bfs(board, i, col-1);83 84 }85 86 for(int i = 0; i < row; i++)87 {88 for(int j = 0; j < col; j++)89 {90 if(board[i][j] == ‘O‘)91 board[i][j] = ‘X‘;92 else if(board[i][j] == ‘*‘)93 board[i][j] = ‘O‘;94 }95 }96 97 98 }99 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。