130. 被围绕的区域

Problem: 130. 被围绕的区域

思路

本题思路与飞地的数量有异曲同工之妙。

都是寻找与四周的边相连接的岛屿,除了这些岛屿之外都是被围绕的区域(在上面的题目中那成为飞地)。

我们用深度优先搜索,搜索四条边,将与四条边相连接的岛屿打上特殊标记A。

那么剩下的岛屿都是飞地。

我们在遍历一次,将飞地O变为海洋X,再将特殊标记A变为原来的陆地O;

记住这两者顺序不要调换哦,因为A -> O -> X。

要注意的一点是:
不要再上下(左右)边的遍历写错了!!!
写错会报错空指针(堆空间溢出)

//从左右 将 O 变为 Q
for(int i = 0; i < board.size(); i++) {
    if(board[i][0] == 'O') dfs(board,i,0);
    if(board[i][board[0].size()-1] == 'O') dfs(board,i, board[0].size()-1);
}
cout << "1step" << endl;
//从上下 将 O 变为 Q 
for(int i = 0; i < board[0].size(); i++) {
    if(board[0][i] == 'O') dfs(board,0,i);
    if(board[board.size()-1][i] == 'O') dfs(board,board.size()-1,i);
}

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

class Solution {
public:
    void dfs(vector<vector<char>>& grid, int x, int y) {
        // cout << "looping"  << "x: " << x << "y" << y << endl;
        grid[x][y] = 'A';
        pair<int, int> neigbors[4]{
            pair<int, int>(x, y + 1), pair<int, int>(x + 1, y),
            pair<int, int>(x, y - 1), pair<int, int>(x - 1, y)};
        for (auto item : neigbors) {
            if (item.first < 0 || item.first >= grid.size() || item.second < 0 ||
                item.second >= grid[0].size())
                continue;
            if (grid[item.first][item.second] == 'A' ||
                grid[item.first][item.second] == 'X')
                continue;
            dfs(grid, item.first, item.second);
        }
    }
    void solve(vector<vector<char>>& board) {
        cout << "0step" << endl;
        //从左右 将 O 变为 Q
        for(int i = 0; i < board.size(); i++) {
            if(board[i][0] == 'O') dfs(board,i,0);
            if(board[i][board[0].size()-1] == 'O') dfs(board,i, board[0].size()-1);
        }
        cout << "1step" << endl;
        //从上下 将 O 变为 Q 
        for(int i = 0; i < board[0].size(); i++) {
            if(board[0][i] == 'O') dfs(board,0,i);
            if(board[board.size()-1][i] == 'O') dfs(board,board.size()-1,i);
        }
        cout << "2step" << endl;
        for(int i = 0; i < board.size(); i++) {
            for(int j = 0; j < board[0].size(); j++) {
                if(board[i][j] == 'O') board[i][j] = 'X';
                if(board[i][j] == 'A') board[i][j] = 'O';
            }
        }
        cout << "3step" << endl;
    }
};