leetcode 130. Surrounded Regions 典型的深度优先遍历DFS + 矩阵遍历-蒲公英云

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

- 日理万妓 2022-06-08 05:36 303阅读 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);
        }
    }
};