LeetCode: Surrounded Regions [130]
【题目】
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 X X O O X X X O X X O X X
After running your function, the board should be:
X X X X X X X X X X X X X O X X
【题意】
给定一个二维矩阵,由'X'和'O'填充,本题要求把那些被'X'包围的'O'替换为'X'。注意这里的包围是指四周全然包围。 假设某片'O'区域触及了矩阵的边界。则这片区域就不算被'X'包围。
我们仅仅须要先把触及到边界的'O'区域所有替换成还有一个字母, 比方'M'。矩阵中剩下的'O'区域就肯定是被包围的了。
【思路】
然后,我们扫描矩阵把'O'替换成'X', 把'M'替换回'O'就可以
区域的遍历,使用DFS或BFS
DFS要使用递归,当矩阵非常大的时候easy超时
所以本题使用BFS
【代码】
class Solution {
public:
void O2M(vector<vector<char> >&board, int i, int j){
//从board[i][j]開始。遍历'O'区域,把'O'替换成'M'
int rows=board.size();
int cols=board[0].size();
queue<int> qe;
qe.push(i*cols+j);
board[i][j]='M';
while(!qe.empty()){
int pos = qe.front(); qe.pop();
i=pos/cols;
j=pos%cols;
//推断上方
if(i-1>=0 && board[i-1][j]=='O'){
board[i-1][j]='M'; //注意在将相邻元素填到队列中时,须要将它标记为以訪问,否则以后在确定其它节点的'O'相邻位置时,非常有可能又把这个节点增加到队列中。造成死循环。
qe.push((i-1)*cols + j);
}
//推断下方
if(i+1<rows && board[i+1][j]=='O'){
board[i+1][j]='M';
qe.push((i+1)*cols + j);
}
//推断左方
if(j-1>=0 && board[i][j-1]=='O'){
board[i][j-1]='M';
qe.push(i*cols + j-1);
}
//推断右方
if(j+1<cols && board[i][j+1]=='O'){
board[i][j+1]='M';
qe.push(i*cols + j+1);
}
}
}
void solve(vector<vector<char>> &board) {
int rows=board.size();
if(rows==0)return;
int cols=board[0].size();
if(cols==0)return;
//把临边的'O'区域替换成'M'
//上边
for(int j=0; j<cols; j++){
if(board[0][j]=='O')O2M(board, 0, j);
}
//下边
for(int j=0; j<cols; j++){
if(board[rows-1][j]=='O')O2M(board, rows-1, j);
}
//左边
for(int i=0; i<rows; i++){
if(board[i][0]=='O')O2M(board, i, 0);
}
//右边
for(int i=0; i<rows; i++){
if(board[i][cols-1]=='O')O2M(board, i, cols-1);
}
//扫描矩阵。把O替换成X, 把M替换成O
for(int i=0; i<rows; i++){
for(int j=0; j<cols; j++){
if(board[i][j]=='O')board[i][j]='X';
else if(board[i][j]=='M')board[i][j]='O';
}
}
}
};
相关文章
- Leetcode 之Construct Binary Tree(52)
- Java实现 LeetCode 799 香槟塔 (暴力模拟)
- Java实现 LeetCode 784 字母大小写全排列(DFS)
- Java实现 LeetCode 696 计数二进制子串(暴力)
- Java实现 LeetCode 653 两数之和 IV - 输入 BST(递归,找差值)
- Java实现 LeetCode 477 汉明距离总和
- Java实现 LeetCode 307 区域和检索 - 数组可修改
- Java实现 LeetCode 239 滑动窗口最大值
- Java实现 LeetCode 130 被围绕的区域
- Java实现 LeetCode 130 被围绕的区域
- Java实现 LeetCode 109 有序链表转换二叉搜索树
- Java实现LeetCode_0013_RomanToInteger
- Leetcode学习计划之动态规划入门day13(931,120)
- Leetcode 693. 交替位二进制数(结束)
- Leetcode 1603. 设计停车系统
- Leetcode 1189. “气球” 的最大数量
- Leetcode 1328. 破坏回文串(可以,已解决)
- Leetcode_num3_Same Tree
- leetcode 226. Invert Binary Tree
- 【Leetcode刷题Python】牛客. 数组中未出现的最小正整数