自动搬运

查看原文

来自洛谷，原作者为

	ckx 理想如晨星，——我们永不能触到，但我们可像航海者一样，借星光的位置而航行。

搬运于2025-08-24 22:57:24，当前版本为作者最后更新于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;
}