leetcode 130. Surrounded Regions 典型的深度优先遍历DFS + 矩阵遍历

- 日理万妓 2022-06-08 05:36 132阅读 0赞

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

For example,  
X X X X  
X O O X  
X X O X  
X O X X  
After running your function, the board should be:

X X X X  
X X X X  
X X X X  
X O X X

从矩形最外面一圈开始逐渐向里拓展。 若 O 是在矩形最外圈，它肯定不会被 X 包围，与它相连（邻）的 O 也就不可能被 X 包围，也就不会被替换，所以我们的工作主要是找出：  
1）最外圈的 O  
2）与最外圈的 O 相连的 O  
3） 将上述找到的元素替换为某种标识符，代码中使用“\#”  
4.）最后按先行后列的顺序遍历矩形，找到没有被替换为 O 的元素，它们就是被 X 完全包围的需要被替换为 X 的元素；同时，标记为 \# 的元素是没有被 X 包围的元素，此时将它们变回原来的 O

这道题的亮点是从问题的对立面来考虑做得，是很经典的DFS深度优先遍历的做法，很棒

代码如下：

import java.util.Stack;
    
    class Point
    {
        int row;
        int col;
        Point(int a,int b)
        {
            row = a;
            col =b;
        }
    }
    
    /*
     * 这个用来学习BFS和DFS很有用
     * 
     * 本题是要求把所有的内部的O替换为X，但是矩阵边界的O不算，
     * 本题是从反面来考虑的，把所有不能替换的O使用*来做一个标记
     * 
     * 本题是通过stack来完成深度优先遍历的，使用BFS或者递归去做
     * 是同样的做法
     * 
     * */
    public class Solution
    {
        
        public void solve(char[][] board) 
        {
            if(board==null || board.length<=0)
                return;
    
            int row = board.length;
            int col = board[0].length;
            if(row<=2 || col<=2)
                return;
            boolean [][]visit = new boolean[row][col];
    
            for(int i=0;i<row;i++)
            {
                for(int j=0;j<col;j++)
                {
                    if(board[i][j]=='O')
                    {
                        if(i==0||i==row-1 ||j==0||j==col-1)
                            dfs(visit,board,i,j,row,col);
                    }
                }
            }
    
            for(int i=0;i<row;i++)
            {
                for(int j=0;j<col;j++)
                {
                    if(board[i][j]=='*')
                        board[i][j]='O';
                    else if(board[i][j]=='O')
                        board[i][j]='X';
                }
            }
        }
    
        private void dfs(boolean [][]visit,char[][] board, int x, int y, int row, int col) 
        {
            board[x][y]='*';
            Stack<Point> stack = new Stack<>();
            stack.push(new Point(x,y));
            visit[x][y]=true;
    
            while(stack.empty()==false)
            {
                Point top = stack.peek();
                stack.pop();
                if(top.row>0 && board[top.row-1][top.col]=='O' && visit[top.row-1][top.col]==false)
                {
                    board[top.row-1][top.col]='*';
                    visit[top.row-1][top.col]=true;
                    stack.push(new Point(top.row-1, top.col));
                }
    
                if(top.row+1<row && board[top.row+1][top.col]=='O' && visit[top.row+1][top.col]==false)
                {
                    board[top.row+1][top.col]='*';
                    visit[top.row+1][top.col]=true;
                    stack.push(new Point(top.row+1, top.col));
                }
    
                if(top.col>0 && board[top.row][top.col-1]=='O' && visit[top.row][top.col-1]==false)
                {
                    board[top.row][top.col-1]='*';
                    visit[top.row][top.col-1]=true;
                    stack.push(new Point(top.row, top.col-1));
                }
    
                if(top.col+1<col && board[top.row][top.col+1]=='O' && visit[top.row][top.col+1]==false)
                {
                    board[top.row][top.col+1]='*';
                    visit[top.row][top.col+1]=true;
                    stack.push(new Point(top.row, top.col+1));
                }   
            }
        }
    }

下面是C++的做法，就是做一个DFS深度优先遍历，不过这道题我们是反其道而行之，通过寻找不符合条件的O，标记为\*，然后把剩下的O填充为X即可完成本体的所有要求

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        void solve(vector<vector<char>>& b) 
        {
            if (b.size() <= 0)
                return;
            int row = b.size(), col = b[0].size();
            vector<vector<bool>> visit(row, vector<bool>(col, false));
            for (int i = 0; i < row; i++)
            {
                for (int j = 0; j < col; j++)
                {
                    if (i == 0 || i == row - 1 || j == 0 || j == col - 1)
                        dfs(b,visit, i, j);
                }
            }
    
            for (int i = 0; i < row; i++)
            {
                for (int j = 0; j < col; j++)
                {
                    if (b[i][j] == 'O')
                        b[i][j] = 'X';
                    else if(b[i][j] == '*')
                        b[i][j] = 'O';
                }
            }
        }
    
        void dfs(vector<vector<char>>& b, vector<vector<bool>>& visit, int x, int y)
        {
            int row = b.size(), col = b[0].size();
            if (x < 0 || x >= row || y < 0 || y >= col || visit[x][y] == true || b[x][y] != 'O')
                return;
            else
            {
                visit[x][y] = true;
                b[x][y] = '*';
                dfs(b, visit, x - 1, y);
                dfs(b, visit, x + 1, y);
                dfs(b, visit, x, y - 1);
                dfs(b, visit, x, y + 1);
            }
        }
    };