首页 > 代码库 > Surrounded Regions

Surrounded Regions

2024-07-17 09:31:54   222人阅读

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‘能被这些点达到，则说明其未被‘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 };

 


联系
我们