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

LeetCode130-被围绕的区域(广度优先搜寻)

程序员文章站 2022-05-20 20:21:24
...

1.题目描述

给定一个二维的矩阵,包含 'X' 和 'O'字母 O)。找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O' 用 'X' 填充。

示例1

输入:
X X X X
X O O X
X X O X
X O X X
运行你的函数后,矩阵变为:

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

解释:被围绕的区间不会存在于边界上,换句话说,任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上,或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。

示例2:

输入:
X O X X
O O O O
X O X X

变换后:
X O X X
O O O O
X O X X

2.实现思路

  • 如果输入矩阵的行数或列数小于3,直接返回;
  • 先扫描边界,将边界为'O'的位置记录到队列,并将其改为'*';
  • 广度优先搜寻,将所有与边界上'O'相邻的点改为'*';
  • 遍历整个数组,将'O'改为'X',将'*'改为'O'。

3.C++代码实现

class Solution {
public:
    struct pos
    {
        int x, y;
    };
    
    void solve(vector<vector<char>>& board) {
        int row = board.size();
        if(row == 0)
            return;
        int col = board[0].size();
        
        if(row <= 2 || col <= 2)
            return;
        
        queue<pos> mypos;
        for(int i = 0; i < col; i++)
        {
            if(board[0][i] == 'O')
            {
                visit(mypos, 0, i, board);
            }
            if(board[row-1][i] == 'O')
            {
                visit(mypos, row-1, i, board);
            }
        }
        for(int i = 1; i < row-1; i++)
        {
            if(board[i][0] == 'O')
            {
                visit(mypos, i, 0, board);
            }
            if(board[i][col-1] == 'O')
            {
                visit(mypos, i, col-1, board);
            }
        }
        

        while(!mypos.empty())
        {
            pos t = mypos.front();
            mypos.pop();
            if(t.x-1 >= 0 && board[t.x-1][t.y] == 'O')
                visit(mypos, t.x-1, t.y, board);
            if(t.x+1 < row && board[t.x+1][t.y] == 'O')
                visit(mypos, t.x+1, t.y, board);
            if(t.y-1 >= 0 && board[t.x][t.y-1] == 'O')
                visit(mypos, t.x, t.y-1, board);
            if(t.y+1 < col && board[t.x][t.y+1] == 'O')
                visit(mypos, t.x, t.y+1, board);
        }

        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(board[i][j] == 'O')
                    board[i][j] = 'X';
                
                else if(board[i][j] == '*')
                    board[i][j] = 'O';
            }
        }
    }
private:
    void visit(queue<pos> &mypos, int x, int y, vector<vector<char>>& board)
    {
        pos p={x, y};
        mypos.push(p);
        board[x][y] = '*';
    }
};