题解：P16439 [XJTUPC 2026] 鲜艳 / 方格

wrong_accept · 2026-05-11 16:41:48 · 题解

本篇题解是 BFS。

::::info[题意]{open} 给了一个 n \times m 的 包含 0 和 1 网格。

然后要判断每个 0 或 1 连通块是不是矩形。 :::: ::::info[矩形的条件]{open}

1. 四联通。
2. 行编号集合是连续的 [r1, r2]，列编号集合是连续的 [c1, c2]，是这些行、列的所有格子，没有空缺。

这里有一种简单、等价的方法：

1. 记录最小行、最大行、最小列、最大列。
2. 计算矩形内的格子数，应等于此连通块的实际格子数。
3. 边界内不能有别的颜色。

这里我考虑再次优化：

如果一个连通块是矩形，那么在最大最小行和列之间的格子必须全是它的颜色，且矩形内部不能有其他颜色的格子，也不能有与它同色但不属于它的连通块。

然后用 BFS 标记验证。 :::: ::::success[算法步骤]{open} 对 n \times m 网格，对颜色 0 或 1 分别 BFS 找连通块。

对每个连通块：

• 记录连通块 x,X,y,Y。
• 计算格子数：(x - X + 1) \cdot (y - Y + 1)。
• 记录实际格子数。
• 检查矩形内的所有格子是否都是该块的颜色，并且在 BFS 过程中标记过属于该块。
• 不是，返回 No。

所有块通过则 Yes。

时间复杂度 O(t \cdot n \cdot m)。 :::: ::::success[AC code]{open}

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 5e2 + 5;
int n, m;
char a[N][N];
bool v[N][N];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void bfs(int sx, int sy, char c, int &x, int &X, int &y, int &Y, int &cnt){
    queue<pair<int, int>> q;
    q.push({sx, sy}), v[sx][sy] = true, x = X = sx, y = Y = sy, cnt = 1;
    while(!q.empty()){
        auto [x, y] = q.front();
        q.pop();
        for(int d = 0; d < 4; d++){
            int nx = x + dx[d], ny = y + dy[d];
            if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && !v[nx][ny] && a[nx][ny] == c)
                v[nx][ny] = true, cnt++, x = min(x, nx), X = max(X, nx), y = min(y, ny), Y = max(Y, ny), q.push({nx, ny});
        }
    }
}

bool check(char color){
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(a[i][j] == color && !v[i][j]){
                int x, X, y, Y, cnt;
                bfs(i, j, color, x, X, y, Y, cnt);
                int rectArea = (X - x + 1) * (Y - y + 1);
                if(rectArea != cnt)
                    return false;
                for(int r = x; r <= X; r++)
                    for(int c = y; c <= Y; c++)
                        if(a[r][c] != color)
                            return false;
            }
    return true;
}

int main() {
    int t;
    scanf("%d", &t);
    while(t--){
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++)
            scanf("%s", a[i] + 1);
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                v[i][j] = false;
        bool c0 = check('0');
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                v[i][j] = false;
        bool c1 = check('1');
        if(c0 && c1)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

::::