[Leetcode]130. Surrounded Regions(C++)

题目描述

Given an m x n matrix board containing 'X' and 'O', capture all regions surrounded by 'X'.

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

例子

例子 1

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.

Follow Up

Note

Constraints

m == board.length

n == board[i].length

1 <= m, n <= 200

board[i][j] is 'X' or 'O'

解题思路

和 [Leetcode]200. Number of Islands(C++) 的思路类似，用 dfs 来对区域进行搜索。在搜索的同时需要对当前格子进行判断是否在边缘如果在则表明当前区域不需要更改，因此还需要用一个列表来维护当前区域包含的格子。

代码如下：

#include <vector>

class Solution {
public:
    void solve(std::vector<std::vector<char>>& board) {
        int m = board.size();
        int n = board[0].size();
        std::vector<std::vector<bool>> visited(m, std::vector<bool>(n, false));

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (!visited[i][j] && board[i][j] == 'O') {
                    bool is_surrounded = true;
                    std::vector<std::pair<int, int>> grid_list;
                    dfs(board, i, j, visited, is_surrounded, grid_list);

                    if (is_surrounded) {
                        for (auto grid : grid_list) {
                            board[grid.first][grid.second] = 'X';
                        }
                    }
                }
            }
        }
    }

private:
    void dfs(std::vector<std::vector<char>>& board, int row, int col,
             std::vector<std::vector<bool>>& visited, bool& is_surrounded,
             std::vector<std::pair<int, int>>& grid_list) {
        if (row == 0 || row == board.size() - 1 || col == 0 ||
            col == board[0].size() - 1) {
            is_surrounded = false;
        }
        visited[row][col] = true;
        grid_list.push_back({row, col});
        std::vector<std::pair<int, int>> dirs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        for (auto& dir : dirs) {
            int r = row + dir.first;
            int c = col + dir.second;
            if (r < 0 || c < 0 || r >= board.size() || c >= board[0].size()) {
                continue;
            }

            if (!visited[r][c] && board[r][c] == 'O') {
                dfs(board, r, c, visited, is_surrounded, grid_list);
            }
        }
    }
};

时间复杂度: O(mn)
空间复杂度：O(mn)

GitHub 代码同步地址： 130.SurroundedRegions.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions