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

sflsDUNN · 2026-05-12 06:36:04 · 题解

看到连通块的题，一眼搜索。

题目大意

给定一个棋盘，判断每个连通块是不是都是矩形。

思路

考虑 dfs。

读入以后，第一步，先循环遍历每一个点。

对于每一个点，如果它已经被访问过了，那就跳到下一个点；否则，在这个点的基础上开始搜索，搜一个连通块，判断是不是矩形。

判断是不是矩形也很简单：搜到每一个点，就把计数器加上 1，顺便统计连通块 x 坐标和 y 坐标的最小值和最大值，分别记为 x_{\min},x_{\max},y_{\min},y_{\max}。如果计数器刚好等于 (x_{\max}-x_{\min}+1)\times(y_{\max}-y_{\min}+1)，就说明这个连通块是满足的，接着循环；否则，直接退出，输出 No。

搜索时别忘了标记是否访问过。

代码

#include <bits/stdc++.h>
using namespace std;

char a[505][505];
int dx[5] = {0, 0, 0, -1, 1};
int dy[5] = {0, 1, -1, 0, 0};
int n, m, vis[505][505], cnt, maxx, maxy, minx, miny;
inline int read(){
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-'){
            f = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
void dfs(int x, int y, char c){
    if (x < 1 || x > n || y < 1 || y > m){//边界
        return;
    }
    vis[x][y] = 1;//是否访问过
    cnt++;//计数器
    maxx = max(maxx, x);
    maxy = max(maxy, y);
    minx = min(minx, x);
    miny = min(miny, y);//更新最小和最大值
    for (int i = 1; i <= 4; i++){//向四个方向搜索
        int nx = x + dx[i], ny = y + dy[i];
        if (!vis[nx][ny] && c == a[nx][ny]){
            dfs(nx, ny, c);
        }
    }
}

int main(){
    int T = read();
    while (T--){
        n = read(), m = read();
        memset(vis, 0, sizeof(vis));//初始化！
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                cin >> a[i][j];
            }
        }
        bool flag = true;
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                if (!vis[i][j]){
                    cnt = 0;
                    minx = maxx = i;
                    miny = maxy = j;//初始化！
                    dfs(i, j, a[i][j]);
                    if (cnt != (maxx - minx + 1) * (maxy - miny + 1)){
                        flag = false;
                    }
                }
            }
            if (!flag){
                break;
            }
        }
        cout << (flag ? "Yes" : "No") << endl;
    }
    return 0;
}

竟然不用开 long long。

完结撒花！