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

· · 题解

题解：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;
}