G7004 [GESP202403 七级] 俄罗斯方块 题解

知识点：洪水填充、形状归一化、集合。

解题思路

洪水填充提取每个四连通同值块，以块内第一个按行列出现的格子为原点记录相对坐标，排序后放入形状集合。

为什么正确

同形状的平移保留全部相对坐标，排序消除遍历顺序影响；不同坐标集合不能通过平移重合。

易错点

只按平移去重，不能自行加入旋转或翻转；不同数值但同形状按题面归为同类。

复杂度

设总格数N，时间O(N log N)上界，空间O(N)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<vector<int>>a(n,vector<int>(m)),vis(n,vector<int>(m));
    for(auto &row:a)for(int &x:row)cin>>x;
    set<vector<pair<int,int>>>types;
    int dr[]= {
        -1,1,0,0
    }
    ,dc[]= {
        0,0,-1,1
    }
    ;
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(!vis[i][j]) {
        vector<pair<int,int>>q= {
            {
                i,j
            }
        }
        ,shape;
        vis[i][j]=1;
        for(int k=0;k<(int)q.size();k++) {
            auto [u,v]=q[k];
            shape.push_back({u-i,v-j});
            for(int z=0;z<4;z++) {
                int x=u+dr[z],y=v+dc[z];
                if(x>=0&&x<n&&y>=0&&y<m&&!vis[x][y]&&a[x][y]==a[i][j]) {
                    vis[x][y]=1;
                    q.push_back({x,y});
                }
            }
        }
        sort(shape.begin(),shape.end());
        types.insert(shape);
    }
    cout<<types.size();
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。