首页 > 代码库 > Surrounded Regions
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 XAfter running your function, the board should be:
X X X XX X X XX X X XX O X X思路：取输入矩阵四周边界上的‘O‘点，若矩阵中间的某个‘O‘能被这些点达到，则说明其未被‘X‘围死。
为了实现上述算法，我们使用队列来保存当前可进行扩展的‘O‘的索引。每次取出队首元素，对其上、下、左、右侧的邻居进行扩展，某邻居需要入队的条件为：该邻居未被访问过，且其取值为‘O‘。该方法本质上是图的广度优先遍历（BFS）。
1 class Solution { 2 public: 3 void solve( vector<vector<char>> &board ) { 4 if( board.size() <= 2 || board[0].size() <= 2 ) { return; } 5 int rows = board.size(), cols = board[0].size(); 6 vector<vector<char>> flip_board( rows, vector<char>( cols, ‘#‘ ) ); 7 list<pair<int,int>> candidates; 8 // 将左、右边界上的‘O‘加入candidates队列。 9 for( int i = 0; i < rows; ++i ) {10 flip_board[i][0] = board[i][0];11 flip_board[i][cols-1] = board[i][cols-1];12 if( board[i][0] == ‘O‘ ) { candidates.push_back( pair<int,int>(i,0) ); }13 if( board[i][cols-1] == ‘O‘ ) { candidates.push_back( pair<int,int>(i,cols-1) ); }14 }15 // 将上、下边界上的‘O‘加入candidates队列。16 for( int j = 1; j < cols-1; ++j ) {17 flip_board[0][j] = board[0][j];18 flip_board[rows-1][j] = board[rows-1][j];19 if( board[0][j] == ‘O‘ ) { candidates.push_back( pair<int,int>(0,j) ); }20 if( board[rows-1][j] == ‘O‘ ) { candidates.push_back( pair<int,int>(rows-1,j) ); }21 }22 // 取队首元素，对其上、下、左、右侧的邻居进行扩展。扩展条件为：该邻居未被访问过，即flip_board[i][j]为‘#‘，且该邻居取值为‘O‘。23 while( !candidates.empty() ) {24 int x = candidates.front().first, y = candidates.front().second;25 candidates.pop_front();26 if( x-1 >= 0 && flip_board[x-1][y] == ‘#‘ ) {27 flip_board[x-1][y] = board[x-1][y];28 if( board[x-1][y] == ‘O‘ ) { candidates.push_back( pair<int,int>(x-1,y) ); }29 }30 if( x+1 < rows && flip_board[x+1][y] == ‘#‘ ) {31 flip_board[x+1][y] = board[x+1][y];32 if( board[x+1][y] == ‘O‘ ) { candidates.push_back( pair<int,int>(x+1,y) ); }33 }34 if( y-1 >= 0 && flip_board[x][y-1] == ‘#‘ ) {35 flip_board[x][y-1] = board[x][y-1];36 if( board[x][y-1] == ‘O‘ ) { candidates.push_back( pair<int,int>(x,y-1) ); }37 }38 if( y+1 < cols && flip_board[x][y+1] == ‘#‘ ) {39 flip_board[x][y+1] = board[x][y+1];40 if( board[x][y+1] == ‘O‘ ) { candidates.push_back( pair<int,int>(x,y+1) ); }41 }42 }43 for( int i = 0; i < rows; ++i ) {44 for( int j = 0; j < cols; ++j ) {45 if( flip_board[i][j] == ‘#‘ ) { flip_board[i][j] = ‘X‘; }46 }47 }48 board = flip_board;49 return;50 }51 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。