CF1966B Rectangle Filling 题解

题目链接：Rectangle Filling

题意：

给定一个 $n\times m(1 \le n, m \le 500)$ 的方格矩阵，每个格子是黑色或白色的。

你可以执行若干次以下操作：

• 选择两个颜色相同的位置 $(x_1,y_1),(x_2,y_2)$
• 将由这两个点构成的矩形区域染成 $(x_1,y_1)$ 对应的颜色。

$1 \le t \le 10^4,\sum nm \le 3\times 10^5$​ 。

显然，如果矩阵的四角中，存在对角颜色相同，则一定有解。

于是只剩下了这四种情况

比如对于第一种情况，我们只需要第一行有个黑的格子（四角除外），或者第 $n$ 行有个白的格子，就有解了

时间复杂度 $\mathcal{O}(\sum nm)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(555))
#define Fi first
#define Se second

char s[N][N];
queue<pii> q;
void solve()
{
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> (s[i] + 1);
    char a = s[1][1], b = s[1][m], c = s[n][1], d = s[n][m];
    if(a == d || b == c) return cout << "YES\n", void(0);
    if(a == b && c == d)
    {
        for(int i = 2; i < m; i++) if(s[n][i] == a) return cout << "YES\n", void(0);
        for(int i = 2; i < m; i++) if(s[1][i] == c) return cout << "YES\n", void(0);
    }else if(a == c && b == d)
    {
        for(int i = 2; i < n; i++) if(s[i][m] == a) return cout << "YES\n", void(0);
        for(int i = 2; i < n; i++) if(s[i][1] == b) return cout << "YES\n", void(0);
    }
    cout << "NO\n";
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}