QOJ #5070. Check Pattern is Bad 题解

Description

庞教授得到一个 $n \times m$ 的棋盘。棋盘上的一些格子被染成了黑色，一些格子被染成了白色，还有一些格子尚未染色。

庞教授不喜欢“棋盘格”图案，因此他想把所有未染色的格子都染色，要求最终棋盘上不存在棋盘格图案。

如果某个 $2 \times 2$ 的正方形由 4 个格子组成，并且它们的染色情况如下之一，则称其出现了棋盘格图案：

$$\begin{matrix} \textsf{B} & \textsf{W} \\ \textsf{W} & \textsf{B} \end{matrix} \quad \text{或} \quad \begin{matrix} \textsf{W} & \textsf{B} \\ \textsf{B} & \textsf{W} \end{matrix}$$

$n,m\leq 100,\sum nm\leq 10^6$。

Solution

首先把 $(i+j)\bmod 2=1$ 的格子翻转颜色，限制变为不能存在一个大小为 $2\times 2$ 的子矩阵颜色完全相同。

如果现在存在一个矩形确定了 $3$ 个颜色，且这 $3$ 个颜色相同，则第四个格子的颜色就确定了。

我们把这些确定的格子加进队列里更新，直到不存在这样的格子。

然后对于还没有确定的格子随便选一个并随便确定一个颜色加入队列，再重复之前的做法是对的。

证明就考虑不合法的最后一步一定形如 $\begin{bmatrix}0&0\\0 & ? & 1\\ &1 & 1\end{bmatrix}$，假设上一步确定的是 $0$，则在这之前一定没有动过那 $3$ 个 $1$，所以右下角的 $\begin{bmatrix}?&1\\1 & 1\end{bmatrix}$ 是一开始就存在的。显然矛盾。

暴力模拟这个做法即可。

时间复杂度：$O(nm)/O(nm\log n)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 105;

int n, m;
int a[kMaxN][kMaxN];
std::string s[kMaxN];

void dickdreamer() {
  std::cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    std::cin >> s[i];
    s[i] = " " + s[i];
    for (int j = 1; j <= m; ++j) {
      if (s[i][j] == 'W') a[i][j] = 0;
      else if (s[i][j] == 'B') a[i][j] = 1;
      else a[i][j] = -1;
      if ((i + j) % 2 && a[i][j] != -1) a[i][j] = 1 - a[i][j];
    }
  }
  std::queue<std::tuple<int, int, int>> q;
  std::set<std::pair<int, int>> st;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (a[i][j] == -1) st.emplace(i, j);
    }
  }
  for (int i = 1; i < n; ++i) {
    for (int j = 1; j < m; ++j) {
      int sum = a[i][j] + a[i][j + 1] + a[i + 1][j] + a[i + 1][j + 1];
      int cnt = (a[i][j] == -1) + (a[i][j + 1] == -1) + (a[i + 1][j] == -1) + (a[i + 1][j + 1] == -1);
      if (!cnt && (sum == 4 || sum == 0)) return void(std::cout << "NO\n");
      if (cnt != 1) continue;
      int v = (sum + 1) != 3;
      if (a[i][j] == -1 && (sum + 1 == 3 || sum + 1 == 0)) a[i][j] = v, st.erase({i, j}), q.emplace(i, j, (sum + 1) != 3);
      if (a[i][j + 1] == -1 && (sum + 1 == 3 || sum + 1 == 0)) a[i][j + 1] = v, st.erase({i, j + 1}), q.emplace(i, j + 1, (sum + 1) != 3);
      if (a[i + 1][j] == -1 && (sum + 1 == 3 || sum + 1 == 0)) a[i + 1][j] = v, st.erase({i + 1, j}), q.emplace(i + 1, j, (sum + 1) != 3);
      if (a[i + 1][j + 1] == -1 && (sum + 1 == 3 || sum + 1 == 0)) a[i + 1][j + 1] = v, st.erase({i + 1, j + 1}), q.emplace(i + 1, j + 1, (sum + 1) != 3);
    }
  }
  for (; !q.empty() || !st.empty();) {
    if (q.empty()) {
      auto [x, y] = *st.begin();
      q.emplace(x, y, 0), st.erase({x, y});
      a[x][y] = 0;
    }
    auto [x, y, v] = q.front(); q.pop();
    for (int i = std::max(x - 1, 1); i <= std::min(x, n - 1); ++i) {
      for (int j = std::max(y - 1, 1); j <= std::min(y, m - 1); ++j) {
        int sum = a[i][j] + a[i][j + 1] + a[i + 1][j] + a[i + 1][j + 1];
        int cnt = (a[i][j] == -1) + (a[i][j + 1] == -1) + (a[i + 1][j] == -1) + (a[i + 1][j + 1] == -1);
        if (!cnt && (sum == 4 || sum == 0)) return void(std::cout << "NO\n");
        if (cnt != 1) continue;
        int v = (sum + 1) != 3;
        if (a[i][j] == -1 && (sum + 1 == 3 || sum + 1 == 0)) a[i][j] = v, st.erase({i, j}), q.emplace(i, j, (sum + 1) != 3);
        if (a[i][j + 1] == -1 && (sum + 1 == 3 || sum + 1 == 0)) a[i][j + 1] = v, st.erase({i, j + 1}), q.emplace(i, j + 1, (sum + 1) != 3);
        if (a[i + 1][j] == -1 && (sum + 1 == 3 || sum + 1 == 0)) a[i + 1][j] = v, st.erase({i + 1, j}), q.emplace(i + 1, j, (sum + 1) != 3);
        if (a[i + 1][j + 1] == -1 && (sum + 1 == 3 || sum + 1 == 0)) a[i + 1][j + 1] = v, st.erase({i + 1, j + 1}), q.emplace(i + 1, j + 1, (sum + 1) != 3);
      }
    }
  }
  std::cout << "YES\n";
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if ((i + j) % 2 && a[i][j] != -1) a[i][j] = 1 - a[i][j];
      if (a[i][j] == 0) std::cout << 'W';
      else if (a[i][j] == 1) std::cout << 'B';
      else std::cout << '?';
    }
    std::cout << '\n';
  }
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}