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]....
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
推荐阅读