[Leetcode] #130 Surrounded Regions

Discription

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

Solution

只有边界上'O'的位置组成的片区不会被'X'包围。因此先对边界上的'O'遍历之后暂存为'#'。非'#'的'O'即被'X'包围了。再对'#'和'O'分别进行替换。 //BFS void flip(vector<vector<char>>& board, int i, int j){ int m = board.size(); int n = board[0].size(); queue<pair<int, int>> pos; pos.push({ i, j }); while (!pos.empty()){ auto p = pos.front(); pos.pop(); if (0 <= p.first && p.first < m && 0 <= p.second && p.second < n && board[p.first][p.second] == 'O'){ board[p.first][p.second] = '#'; pos.push({ p.first - 1, p.second }); pos.push({ p.first + 1, p.second }); pos.push({ p.first, p.second - 1 }); pos.push({ p.first, p.second + 1 }); } } } void solve(vector<vector<char>>& board) { if (board.size() <= 1 || board[0].size() <= 1) return; for (int i = 0; i < board.size(); i++){ flip(board, i, 0); flip(board, i, board[i].size()-1); } for (int i = 0; i < board[0].size(); i++){ flip(board, 0, i); flip(board, board.size() - 1, i); } for (int i = 0; i < board.size(); i++){ for (int j = 0; j < board[0].size(); j++){ if (board[i][j] == '#') board[i][j] = 'O'; else if (board[i][j] == 'O') board[i][j] = 'X'; } } } //DFS 会超时 void flip(vector<vector<char>>& board, int i, int j){ if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != 'O') return; board[i][j] = '#'; flip(board, i - 1, j); flip(board, i + 1, j); flip(board, i, j - 1); flip(board, i, j + 1); } void solve(vector<vector<char>>& board) { if (board.size() <= 1 || board[0].size() <= 1) return; for (int i = 0; i < board.size(); i++){ flip(board, i, 0); flip(board, i, board[i].size()-1); } for (int i = 0; i < board[0].size(); i++){ flip(board, 0, i); flip(board, board.size() - 1, i); } for (int i = 0; i < board.size(); i++){ for (int j = 0; j < board[0].size(); j++){ if (board[i][j] == '#') board[i][j] = 'O'; else if (board[i][j] == 'O') board[i][j] = 'X'; } } }GitHub-Leetcode: https://github.com/wenwu313/LeetCode