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