130.surrounded-regions
Statement
Metadata
- Link: 被围绕的区域
- Difficulty: Medium
- Tag:
深度优先搜索广度优先搜索并查集数组矩阵
给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
示例 1：
输入：board = [["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：
输入：board = [["X"]]
输出：[["X"]]
提示：
m == board.lengthn == board[i].length1 <= m, n <= 200board[i][j]为'X'或'O'
Metadata
- Link: Surrounded Regions
- Difficulty: Medium
- Tag:
Depth-First SearchBreadth-First SearchUnion FindArrayMatrix
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.lengthn == board[i].length1 <= m, n <= 200board[i][j]is'X'or'O'.
Tutorial
错误做法
- 本来考虑从上到下，从左到右，扫一遍，然后这个时候只维护这个块的上方和左侧是否被包围
- 同理，再从下至上，从右至左，扫一遍，维护这个块的下方和右侧是否被包围
- 然后再扫一遍，如果一个块通过两遍扫描，都被判定为包围，那么认为这个块被包围
但是这样有个问题，比如这个 case
结果会变成
- 问题在于，上方和左侧以及下方和右侧都可以被包围，但是它们并没有联通
还有一个想法，也是错误的，就是将一个 X 的八个方向相邻的 X 都并起来，然后对于一个 O，如果它最上方、最下方、最左侧、最右侧的 X 同属一个联通块，那么认为它应该变成 X
有个例子能够 X 掉这种做法
可以发现，对于 (1, 1) 这个位置的 O，它的上下左右的 X 属于同一个联通块，但是这个联通块不是封闭的
正确做法
考虑边界的 O，如果和边界的 O 相邻的 O，那么一定不能被包围，然后 DFS 或者 BFS 一遍即可。
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
// head
// 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
// head
// 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
// head
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
最后更新: October 11, 2023