欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

LeetCode130被围绕的区域

程序员文章站 2022-03-22 10:11:01
DFS解题思路做DFS的题目时,要考虑四点要素1.从哪里开始2.做什么操作3.下一步该怎么走4.什么时间结束针对这一题从哪里开始是一个很巧妙的class Solution {public: void DFS(vector>& board,int x,int y){ if(x<0||x>=board.size()||y<0||y>=board[0].size()||board[x][y]....

LeetCode130被围绕的区域

DFS解题思路

做DFS的题目时,要考虑四点要素
1.从哪里开始
2.做什么操作
3.下一步该怎么走
4.什么时间结束
针对这一题从哪里开始是一个很巧妙的问题,题目说明‘o’处在边界上时是不会被X包围的,而且与边界‘o’相连的‘o’也是不会被X包围的,只有那些不与边界‘0’相连的‘0’才能被X包围,所以我们选择开始位置时直接选择第一个在边界上的‘o’,当我们搜索完整所有与边界‘o’相连的‘o’,剩下的‘o’就是被X包围的。第二步,把这个位置的‘o’变为除‘o’,‘X’外的其它字符用来标记这个位置的‘o’是边界‘o’。第三步,对这个‘o’的四周进行遍历来寻找与这个‘o’相连的‘o’,此时要注意边界问题,而且如果周围存在‘#’或者‘X’,不用进行操作,返回空就行,遇到‘o’的话就把这个‘o’更换为其他字符。然后在寻找这个‘o’周围是否有‘o’。第四步,当整个数组遍历完,就结束了。

class Solution {
public:
    void DFS(vector<vector<char>>& board,int x,int y){
        if(x<0||x>=board.size()||y<0||y>=board[0].size()||board[x][y]=='X'||board[x][y]=='#')return ;
        board[x][y]='#';
        DFS(board,x-1,y);
        DFS(board,x+1,y);
        DFS(board,x,y-1);
        DFS(board,x,y+1);
    }
    void solve(vector<vector<char>>& board) {
        if(board.size()==0)return ;
        int n=board.size();
        int m=board[0].size();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                bool isEdage=i==0||j==0||i==n-1||j==m-1;
                if(isEdage && board[i][j]=='O'){
                    DFS(board,i,j);
                }
            }
        }

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

    }
};

本文地址:https://blog.csdn.net/qq_44111658/article/details/109237529