首页 > 代码库 > LeetCode: Surrounded Regions
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 XAfter running your function, the board should be:
X X X XX X X XX X X XX O X X
地址：https://oj.leetcode.com/problems/surrounded-regions/
算法：我们必须明确一个事实：所有没有被‘X‘环绕的‘O‘必定有一个从边缘的‘O’跟它联通着，所以我的算法就是从四个边缘为‘O‘的位置开始往内部按BFS的思想将‘O’设置为‘X’。代码：
1 class Solution { 2 public: 3 void solve(vector<vector<char>> &board) { 4 if(board.empty()) return; 5 int m = board.size(); 6 vector<vector<bool> > flag; 7 for(int i = 0; i < m; ++i){ 8 int mi = board[i].size(); 9 flag.push_back(vector<bool>(mi,false));10 }11 for(int i = 0; i < board[0].size(); ++i){12 if(board[0][i] == ‘O‘ && flag[0][i] == false){13 14 solveCore(board,flag,0,i);15 }16 }17 for(int i = 1; i < m; ++i){18 int mi = board[i].size();19 if(mi > 0 && board[i][0] == ‘O‘ && flag[i][0] == false){20 21 solveCore(board,flag,i,0);22 }23 if(mi > 0 && board[i][mi-1] == ‘O‘ && flag[i][mi-1] == false){24 25 solveCore(board,flag,i,mi-1);26 }27 }28 for(int i = 1; i < board[m-1].size()-1; ++i){29 if(board[m-1][i] == ‘O‘ && flag[m-1][i] == false){30 31 solveCore(board,flag,m-1,i);32 }33 }34 for(int i = 0; i < m; ++i){35 int mi = board[i].size();36 for(int j = 0; j < mi; ++j){37 if(board[i][j] == ‘O‘ && !flag[i][j])38 board[i][j] = ‘X‘;39 }40 }41 }42 void solveCore(vector<vector<char> > &board, vector<vector<bool> > &flag, int x, int y){43 queue<pair<int,int> > Q;44 Q.push(pair<int,int>(x,y));45 flag[x][y] = true;46 while(!Q.empty()){47 pair<int,int> pa = Q.front();48 int i = pa.first, j = pa.second;49 if(i > 0 && j < board[i-1].size() && board[i-1][j] == ‘O‘ && flag[i-1][j] == false){50 flag[i-1][j] = true;51 Q.push(pair<int,int>(i-1,j));52 }53 if(j < board[i].size()-1 && board[i][j+1] == ‘O‘ && flag[i][j+1] == false){54 flag[i][j+1] = true;55 Q.push(pair<int,int>(i,j+1));56 }57 if(i < board.size()-1 && j < board[i+1].size() && board[i+1][j] == ‘O‘ && flag[i+1][j] == false){58 flag[i+1][j] = true;59 Q.push(pair<int,int>(i+1,j));60 }61 if(j > 0 && board[i][j-1] == ‘O‘ && flag[i][j-1] == false){62 flag[i][j-1] = true;63 Q.push(pair<int,int>(i,j-1));64 }65 Q.pop();66 }67 }68 };
LeetCode: Surrounded Regions
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。