LeetCode Daily Question 19

Apr 8th 2022

4 月 8 日 每日一题

题目：130. Surrounded Regions

Given an m x n matrix board containing ‘X’ and ‘O’, capture all regions that are 4-directionally surrounded by ‘X’.

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

1
2
3
Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Surrounded regions should not be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

思路

今天这道题和昨天的差不多，在昨天的代码上做一些改动即可。即为进入 BFS 增加一个限制条件（必须在边界），在 BFS 中做好标记。最后循环一遍，将做好标记的点改为 O，其余改为 X。
等下再做一道放上来，这个和昨天的太像了…

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
public:
    struct dequePoint
    {
        uint32_t x = 0;
        uint32_t y = 0;
    };

    bool valid(std::vector<std::vector<char>>& board, uint32_t x, uint32_t y){
        if(x >= 0 && x < board[0].size() && y >= 0 && y < board.size())
            return board[y][x] == 'O' ? true : false;
        return false;
    }
    bool valid1(std::vector<std::vector<char>>& board, uint32_t x, uint32_t y){
        if(x >= 0 && x < board[0].size() && y >= 0 && y < board.size())
            return true;
        return false;
    }

    void bfsHelper(std::vector<std::vector<char>>& board, uint32_t x, uint32_t y){
        queue<dequePoint> queue;
        queue.push(dequePoint{x,y});
        board[y][x] = 'x';
        while(!queue.empty()){
            x = queue.front().x;
            y = queue.front().y;
            queue.pop();
            if(valid(board, x - 1, y)){
                queue.push(dequePoint{x - 1,y});
                board[y][x - 1] = 'x';
            }
            if(valid(board, x + 1, y)){
                queue.push(dequePoint{x + 1,y});
                board[y][x + 1] = 'x';
            }
            if(valid(board, x, y - 1)){
                queue.push(dequePoint{x,y - 1});
                board[y - 1][x] = 'x';
            }
            if(valid(board, x, y + 1)){
                queue.push(dequePoint{x,y + 1});
                board[y + 1][x] = 'x';
            }
        }
    }

    void solve(std::vector<std::vector<char>>& board) {
        for(uint32_t y = 0; y < board.size(); y++){
            for(uint32_t x = 0; x < board[0].size(); x++){
                if(!valid1(board, x - 1, y) || !valid1(board, x + 1, y) ||
                   !valid1(board, x, y - 1) || !valid1(board, x, y + 1)){
                    if(board[y][x] == 'O'){
                        bfsHelper(board, x, y);
                    }
                }
            }
        }
        for(uint32_t y = 0; y < board.size(); y++){
            for(uint32_t x = 0; x < board[0].size(); x++){
                if(board[y][x] == 'x')
                    board[y][x] = 'O';
                else
                    board[y][x] = 'X';
            }
        }
    }
};

,
  1. 4 月 8 日 每日一题
    1. 题目：130. Surrounded Regions
    2. 思路
    3. 代码