自动搬运

查看原文

来自洛谷，原作者为

	sjwhsss **

搬运于2025-08-24 23:14:39，当前版本为作者最后更新于2025-04-26 19:25:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解：P12328 [蓝桥杯 2023 省 Java B] 合并区域

题意：

给定两个 $n\times n$ 的矩阵，每个位置可能是 $0$ 或 $1$，可以对两个矩阵进行 $90$ 度、$180$ 度、$270$ 度、$360$ 度的旋转，上下移动两个矩阵，求将两个矩阵左右拼接后，最大的 $1$ 的联通块的大小。

思路分析

这道题主要在于模拟，思路是将两个数组旋转和平移后 DFS 找联通块。先考虑如何旋转，设原矩阵为 $A$，旋转后矩阵为 $B$ 经过简单模拟后可以发现：逆时针旋转 $90$ 度即 $B_{i,j}=A_{j,n-i+1}$，$180$ 度即 $B_{i,j}=A_{n-i+1,n-j+1}$，$270$ 度即 $B_{i,j}=A_{n-j+1,i}$，显然 $360$ 度就是没旋转。处理完旋转以后，再考虑平移，可以发现我们只需要移动其中一个矩阵就行了。在代码实现中我们可以将合并后的新矩阵的下标设置一个偏移量，方便我们进行旋转和平移，设两个数组分别为 $A,B$，合并后的数组为 $C$ 。对于 $A$，将其存储在 $C$ 的下标满足 $201\le i\le 200+n,201\le j\le200+n$ 的位置，对于 $B$ 设向上平移了 $d$ ，$d$ 为负表示向下平移，那么将其存储在 $200-d+1\le i\le 200-d+n,200+n+1\le j\le 200+2n$ 的位置。这样就不用考虑越界的问题，也不用频繁修改 $A$ 数组。时间复杂度 $O(k\times n^3)$，其中 $k=4\times 4=16$，表示枚举旋转两个数组共 $16$ 种情况。写完后才发现可以只用写一个旋转 $90$ 度的函数，常数可能会小很多。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+5;
int n , m , a[maxn][maxn] , b[maxn][maxn] , c[maxn][maxn] , dir[4][2]={{0 , 1} , {0 , -1} , {1 , 0} , {-1 , 0}} , sum , ans;
bool vis[maxn][maxn];
void Dfs(int x , int y)
{
	vis[x][y]=1;
	sum++;
	for (int i = 0; i < 4; i++)
	{
		int dx = x + dir[i][0] , dy = y + dir[i][1];
		if (vis[dx][dy] ^ 1 && c[dx][dy])Dfs(dx , dy);
	}
	return;
}
void Clear()
{
	for (int i = 200; i <= 301; i++) for (int j = m + 1; j <= 301; j++)c[i][j]=0;
	return;
}
void Work()
{
	for (int i = 200; i <= 301; i++) for (int j = 200; j <= 301; j++)vis[i][j]=0;
	for (int i = 200; i <= 301; i++) for (int j = 200; j <= 301; j++,sum=0) if ((vis[i][j] ^ 1) && c[i][j])Dfs(i , j),ans=max(ans , sum);
	return;
}
void debug()
{
	for (int i = 1; i <= n*2; i++) 
	{
		for (int j = 1; j <= n*2; j++) cout << c[200+i][200+j] << " ";
		cout << endl;
	}
}
void Turn(int st)
{
	Clear();
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			c[200 - st + i][m + j] = b[i][j];
	Work();
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			c[200 - st + i][m + j] = b[j][n - i + 1];
	Work();
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			c[200 - st + i][m + j] = b[n - i + 1][n - j + 1];
	Work();
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			c[200 - st + i][m + j] = b[n - j + 1][i];
	Work();
	return;
}
int main ()
{
	scanf("%d" , &n);
	m = 200 + n;
	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)scanf("%d" , &a[i][j]);
	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)scanf("%d" , &b[i][j]);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			c[200 + i][200 + j] = a[i][j];
	for (int i = -n-1; i <= n+1; i++)Turn(i);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			c[200 + i][200 + j] = a[j][n - i + 1];
	for (int i = -n-1; i <= n+1; i++)Turn(i);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			c[200 + i][200 + j] = a[n - i + 1][n - j + 1];
	for (int i = -n-1; i <= n+1; i++)Turn(i);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			c[200 + i][200 + j] = a[n - j + 1][i];
	for (int i = -n-1; i <= n+1; i++)Turn(i);
	printf("%d\n" , ans);
	return 0;
}