侧边栏壁纸
博主头像
Hope博主等级

努力赚钱的工科研究生

  • 累计撰写 362 篇文章
  • 累计创建 129 个标签
  • 累计收到 5 条评论
标签搜索

LeetCode 130. 被围绕的区域

Hope
2022-02-26 / 0 评论 / 0 点赞 / 199 阅读 / 792 字
温馨提示:
本文最后更新于 2022-02-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

LeetCode 130. 被围绕的区域

思路:

找到边界的 'O',如果与边界的 'O'是相连的,那么一定是不符合的,对这样的'O'坐标做一个标记,然后对有标记的坐标修改为'O',其他修改为'X'。

代码:

class Solution {
public:
    int n,m;
    vector<vector<char>> board;
    int dx[4] = {0,1,0,-1};
    int dy[4] = {1,0,-1,0};

    void solve(vector<vector<char>>& _board) {
        board = _board;
        n = board.size();
        if(!n) return;
        m = board[0].size();

        for(int i=0;i<n;i++){
            if(board[i][0] == 'O') dfs(i,0);
            if(board[i][m-1] == 'O') dfs(i,m-1);
        }

        for(int i = 0;i < m;i++){
            if(board[0][i] == 'O') dfs(0,i);
            if(board[n-1][i] == 'O') dfs(n-1,i);
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(board[i][j] == '#') board[i][j] = 'O';
                else board[i][j] = 'X';
            }
        }

        _board = board;

    }

    void dfs(int x,int y){
        board[x][y] = '#';
        for(int i=0;i<4;i++){
            int a = x + dx[i];
            int b = y + dy[i];
            if(a >=0 && a < n && b >= 0 && b < m && board[a][b] == 'O'){
                dfs(a,b);
            }
        }
    }
};

0

评论区