题目：https://leetcode-cn.com/problems/surrounded-regions/
给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
我的方法一，广度优先搜索
步骤
思路是先找到边上的O，然后深度所有和这个O相连的所有的O；等遍历完了所有边上的O后，剩余没有遍历的O就是被围绕的区域。
- 先将所有的边上的O的坐标存到一个队列里
- 从队列获取一个O，然后对这个O进行深度优先搜索相连的O，搜索到的O也存到这个队列里
- 在这个过程中，有可能一个O可能会被遍历多次，所以为了只遍历一次，所以遍历后，先暂时改为一个特殊的字符，如A
- 当队列里没有O时，即所有的和边相连的O都没有的时候，剩余的O就是被围绕的
- 将所有被围绕的O改为X；将所有的A再改为O
边界条件
- 注意矩阵的长或者宽为0
- 遍历时需要考虑坐标越界
- 当队列为空时，说明所有的和边相连的O遍历完，即停止遍历即可
复杂度
时间复杂度：O(n)，如下代码注释，需要注意深度搜索时，由于使用A对遍历过的O进行特殊标记，所以一个O只会被遍历一次，所以深度搜索也是O(n)。
空间复杂度：队列最多放入n个点，所以也是O(n)。
代码
class Solution {
public:
void solve(vector<vector<char>>& board) {
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int row = board.size();
if(row==0){
return;
}
int col = board[0].size();
if(col==0){
return;
}
//O(n)
queue<pair<int, int>> edge_q;//y, x
for(int x = 0; x<col; x++){
if(board[0][x] == 'O'){
edge_q.emplace(0, x);
}
if(board[row-1][x] == 'O'){
edge_q.emplace(row-1, x);
}
}
for(int y = 0; y<row; y++){
if(board[y][0] == 'O'){
edge_q.emplace(y, 0);
}
if(board[y][col-1] == 'O'){
edge_q.emplace(y, col-1);
}
}
int tmp_y;
int tmp_x;
//dfs, O(n)
while(!edge_q.empty()){
pair<int, int> top = edge_q.front();
edge_q.pop();
board[top.first][top.second] = 'A';
for(int i=0; i<4; i++){
tmp_y = top.first+dy[i];
tmp_x = top.second+dx[i];
if(tmp_y>=0 && tmp_y<row && tmp_x>=0&& tmp_x<col && board[tmp_y][tmp_x] == 'O'){
edge_q.emplace(tmp_y, tmp_x);
}
}
}
//O(n)
for(int x = 0; x<col; x++){
for(int y = 0; y<row; y++){
if(board[y][x] == 'O'){
board[y][x] = 'X';
}
}
}
//O(n)
for(int x = 0; x<col; x++){
for(int y = 0; y<row; y++){
if(board[y][x] == 'A'){
board[y][x] = 'O';
}
}
}
}
};
我的方法二，深度优先搜索
在BFS基础上，稍微改下就是，代码如下
class Solution {
public:
void solve(vector<vector<char>>& board) {
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int row = board.size();
if(row==0){
return;
}
int col = board[0].size();
if(col==0){
return;
}
//O(n)
queue<pair<int, int>> edge_q;//y, x
for(int x = 0; x<col; x++){
if(board[0][x] == 'O'){
edge_q.emplace(0, x);
}
if(board[row-1][x] == 'O'){
edge_q.emplace(row-1, x);
}
}
for(int y = 0; y<row; y++){
if(board[y][0] == 'O'){
edge_q.emplace(y, 0);
}
if(board[y][col-1] == 'O'){
edge_q.emplace(y, col-1);
}
}
while(!edge_q.empty()){
pair<int, int> o = edge_q.front();
edge_q.pop();
dfs(board, row, col, o.first, o.second);
}
//O(n)
for(int x = 0; x<col; x++){
for(int y = 0; y<row; y++){
if(board[y][x] == 'O'){
board[y][x] = 'X';
}
}
}
//O(n)
for(int x = 0; x<col; x++){
for(int y = 0; y<row; y++){
if(board[y][x] == 'A'){
board[y][x] = 'O';
}
}
}
}
private:
void dfs(vector<vector<char>>& board, int row, int col, int y, int x) {
if(y<0 || y>= row || x<0 || x>= col || board[y][x] != 'O'){
return;
}
board[y][x] = 'A';
dfs(board, row, col, y - 1, x);
dfs(board, row, col, y + 1, x);
dfs(board, row, col, y, x - 1);
dfs(board, row, col, y, x + 1);
}
};
我的方法三，迭代版DFS
方法二是一个尾递归，所以很容易改成迭代，代码如下
class Solution {
public:
void solve(vector<vector<char>>& board) {
int row = board.size();
if(row==0){
return;
}
int col = board[0].size();
if(col==0){
return;
}
//O(n)
queue<pair<int, int>> edge_q;//y, x
for(int x = 0; x<col; x++){
if(board[0][x] == 'O'){
edge_q.emplace(0, x);
}
if(board[row-1][x] == 'O'){
edge_q.emplace(row-1, x);
}
}
for(int y = 0; y<row; y++){
if(board[y][0] == 'O'){
edge_q.emplace(y, 0);
}
if(board[y][col-1] == 'O'){
edge_q.emplace(y, col-1);
}
}
while(!edge_q.empty()){
pair<int, int> o = edge_q.front();
edge_q.pop();
stack<pair<int, int>> s;//参数栈
s.push(o);//模拟首次调用dfs设置的参数
pair<int, int> param;
while(!s.empty()){//参数栈为空时，说明递归完成了
param = s.top();
s.pop();
//模拟dfs函数里的判断
if(param.first<0 || param.first>= row || param.second<0 || param.second>= col || board[param.first][param.second] != 'O'){
continue;
}
board[param.first][param.second] = 'A';
//模拟4次调用dfs
s.emplace(param.first - 1, param.second);
s.emplace(param.first + 1, param.second);
s.emplace(param.first, param.second + 1);
s.emplace(param.first, param.second - 1);
}
}
//O(n)
for(int x = 0; x<col; x++){
for(int y = 0; y<row; y++){
if(board[y][x] == 'O'){
board[y][x] = 'X';
}
}
}
//O(n)
for(int x = 0; x<col; x++){
for(int y = 0; y<row; y++){
if(board[y][x] == 'A'){
board[y][x] = 'O';
}
}
}
}
};
网友评论