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

_ckx_ · 2024-05-17 20:14:52 · 题解

题目大意

给定一个 n \times m 的矩阵，求其中不同种类的方块的数量。

定义方块为几个相邻且颜色相同的点组成的连通块。

定义两个方块种类不同为两个方块形状不相同，颜色随意。

思路

先考虑如何判断两个方块是否相同：

定义两个方向数组 dx 和 dy。

可以发现我们只需要判断遍历这两个方块时每个方向是否相等就行了，可以用 string 来存储。

最后用 map 来标记就行了。

这里给大家介绍一下 unordered_map：内部不用排序，插入和查找均摊情况下是 \mathcal{O}(1) 复杂度，最坏 \mathcal{O}(n)，在数据量不多的情况下比 map 快一些。

code

#include <bits/stdc++.h>
#define umap unordered_map
using namespace std;
typedef long long ll;

int n ,m;
const int N = 510;
int a[N][N];
int vis[N][N];
umap<string ,int> mp;

//方向数组 
int dx[] = {1 ,0 ,-1 ,0};
int dy[] = {0 ,1 ,0 ,-1};

void dfs(int x ,int y ,string &s/*&s:取s的地址，可以在函数里直接修改*/)
{
    for (int i = 0;i < 4;i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) //越界判断 
        {
            if (vis[nx][ny] || a[nx][ny] != a[x][y]) continue; //访问过或者颜色不一可以直接跳过 
            s += char(i + '0'); 
            vis[nx][ny] = 1; //标记 
            dfs(nx ,ny ,s);
            //不用回溯，因为不会再次访问 
        }
    }
    s += ' '; //注意：最后要加一个空格，因为转弯地点会发生改变，加空格为了区分不同的转弯地点 
}

int main()
{
    scanf("%d%d",&n ,&m);

    for (int i = 1;i <= n;i++)
    {
        for (int j = 1;j <= m;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }

    int ans = 0;
    for (int i = 1;i <= n;i++)
    {
        for (int j = 1;j <= m;j++)
        {
            if (!vis[i][j]) //没被走过就走 
            {
                vis[i][j] = 1;

                string s = "";
                dfs(i ,j ,s);

                if (!mp[s]) //如果没有这种方块就加一个种类 
                {
                    ans++;
                }
                mp[s] = 1; //标记 
            }
        }
    }

    printf("%d\n",ans);

    return 0;
}