# 130.surrounded-regions

## Statement

• Difficulty: Medium
• Tag: `深度优先搜索` `广度优先搜索` `并查集` `数组` `矩阵`

``````输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

``````

``````输入：board = [["X"]]

``````

• `m == board.length`
• `n == board[i].length`
• `1 <= m, n <= 200`
• `board[i][j]``'X'``'O'`

• Difficulty: Medium
• Tag: `Depth-First Search` `Breadth-First Search` `Union Find` `Array` `Matrix`

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.

Example 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: Notice that an 'O' should not be flipped if:
- It is on the border, or
- It is adjacent to an 'O' that should not be flipped.
The bottom 'O' is on the border, so it is not flipped.
The other three 'O' form a surrounded region, so they are flipped.
``````

Example 2:

``````Input: board = [["X"]]
Output: [["X"]]
``````

Constraints:

• `m == board.length`
• `n == board[i].length`
• `1 <= m, n <= 200`
• `board[i][j]` is `'X'` or `'O'`.

## 错误做法

• 本来考虑从上到下，从左到右，扫一遍，然后这个时候只维护这个块的上方和左侧是否被包围
• 同理，再从下至上，从右至左，扫一遍，维护这个块的下方和右侧是否被包围
• 然后再扫一遍，如果一个块通过两遍扫描，都被判定为包围，那么认为这个块被包围

``````X X O O O
X O O X X
O O X O O
``````

``````X X O O O
X X X X X
O O X O O
``````
• 问题在于，上方和左侧以及下方和右侧都可以被包围，但是它们并没有联通

``````O X O O O
X O O O X
O X O O X
O O X X O
``````

## Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

// correct

// 0 1 1 0
// 1 0 0 1
// 0 1 1 0

// X X X X
// X O O X
// X X O X
// X O X X

class Solution {
public:
bool is_valid_point(int x, int y) {
if (x < 0 || x >= n) {
return false;
}

if (y < 0 || y >= m) {
return false;
}

return true;
}

void dfs(int x, int y, vector<vector<char>> &board) {
board[x][y] = 'B';

for (const auto &d : dir) {
int nx = x + d[0];
int ny = y + d[1];

if (!is_valid_point(nx, ny)) {
continue;
}

if (board[nx][ny] == 'X' || board[nx][ny] == 'B') {
continue;
}

dfs(nx, ny, board);
}
}

void solve(vector<vector<char>> &board) {
n = int(board.size());
m = int(board[0].size());

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == 0 || j == 0 || i == n - 1 || j == m - 1) {
if (board[i][j] == 'O') {
dfs(i, j, board);
}
}
}
}

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}

if (board[i][j] == 'B') {
board[i][j] = 'O';
}
}
}
}

private:
int n, m;

inline const static auto dir = vector<vector<int>>({
{0, 1},
{1, 0},
{-1, 0},
{0, -1},
});
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## Solution1

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

// 0 1 1 0
// 1 0 0 1
// 0 1 1 0

// X X X X
// X O O X
// X X O X
// X O X X

struct Node {
int l{-1}, r{-1}, u{-1}, d{-1};
};

class Solution {
public:
bool is_valid_point(int x, int y) {
if (x < 0 || x >= n) {
return false;
}

if (y < 0 || y >= m) {
return false;
}

return true;
}

void dfs(int x, int y, int cur_color) {
color_[x][y] = cur_color;

for (const auto &d : dir) {
int nx = x + d[0];
int ny = y + d[1];

if (!is_valid_point(nx, ny)) {
continue;
}

if (board_[nx][ny] != 'X') {
continue;
}

if (color_[nx][ny]) {
continue;
}

dfs(nx, ny, cur_color);
}
}

void solve(vector<vector<char>> &board) {
n = int(board.size());
m = int(board[0].size());
board_ = board;

color_ = vector<vector<int>>(n + 5, vector<int>(m + 5, 0));
int max_color = 1;

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == 'X' && color_[i][j] == 0) {
dfs(i, j, max_color);
++max_color;
}
}
}

auto mp = vector<vector<Node>>(n + 5, vector<Node>(m + 5, Node{}));

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == 'X') {
auto node = Node();
node.l = j;
node.r = j;
node.u = i;
node.d = i;

mp[i][j] = node;
} else {
auto node = Node();

if (i) {
node.u = mp[i - 1][j].u;
}

if (j) {
node.l = mp[i][j - 1].l;
}

mp[i][j] = node;
}
}
}

for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
if (board[i][j] != 'X') {
auto &node = mp[i][j];

if (i < n - 1) {
node.d = mp[i + 1][j].d;
}

if (j < m - 1) {
node.r = mp[i][j + 1].r;
}
}
}
}

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
const auto &node = mp[i][j];
if (node.l == -1 || node.r == -1 || node.u == -1 || node.d == -1) {
continue;
}

auto cur_color = color_[i][node.l];
if (color_[i][node.r] != cur_color) {
continue;
}

if (color_[node.u][j] != cur_color) {
continue;
}

if (color_[node.d][j] != cur_color) {
continue;
}

board[i][j] = 'X';
}
}
}

private:
int n, m;
vector<vector<int>> color_;
vector<vector<char>> board_;

inline const static auto dir = vector<vector<int>>({
{0, 1},
{1, 0},
{-1, 0},
{0, -1},
{1, 1},
{1, -1},
{-1, 1},
{-1, -1},
});
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## Solution2

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

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

vector<vector<int>> f(n + 5, vector<int>(m + 5, 0));
vector<vector<int>> g(n + 5, vector<int>(m + 5, 0));

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == 'X') {
f[i][j] = 1;
}

if (i && j) {
if (f[i - 1][j] && f[i][j - 1]) {
f[i][j] = 1;
}
}
}
}

for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
if (board[i][j] == 'X') {
g[i][j] = 1;
}

if (i < n - 1 && j < m - 1) {
if (g[i + 1][j] && g[i][j + 1]) {
g[i][j] = 1;
}
}
}
}

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j]) {
board[i][j] = 'X';
}
}
}
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````