[二维前缀和]最大纯色正方形

题目描述

铺砖的工人来到一个操场，将整个操场按正方形铺砖（整个操场可视为R行C列的矩阵，矩阵的每个元素为一块正方形砖块），正方形砖块有两种，一种为蓝色，另一种为红色。请你写一个程序求出为最大纯色正方形的面积。

输入格式

第一行两个正整数R和C。 接下来R行C列描述整个操场，红色砖块用1来表示，蓝色砖块用0来表示。

输出格式

一个数，表示最大纯色正方形的面积。

样例输入/输出

输入数据 1

5 8
0 0 0 1 1 1 0 1
1 1 0 1 1 1 1 1
0 1 1 1 1 1 0 1
1 0 1 1 1 1 1 0
1 1 1 0 1 1 0 1

输出数据 1

9

数据规模与提示

100%的数据R,C<=200;

时间限制：1s.

内存限制：128MB.

解！！！

这道题可以使用二维前缀和来解决。

首先，我们需要构建一个二维前缀和的数组sum，sum[i][j]表示以(i,j)为右下角的正方形区域内的红色砖块的数量。

我们可以通过以下方式构建sum数组：

1. 遍历每个格子(i,j)，将砖块的颜色e[i][j]保存到数组中，并计算sum[i][j]的值：

sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + e[i][j]

这样，sum数组的每个元素就表示了以(i,j)为右下角的正方形区域内的红色砖块的数量。

接下来，我们需要从最大可能的正方形大小开始遍历，找到一个满足条件的正方形。

假设最大可能的正方形大小为n，我们从n开始递减遍历，对于每个正方形大小k，我们从左上角的位置(x,y)开始遍历操场区域。

具体的遍历方式如下：

1. 遍历所有可能的左上角位置(x,y)，满足条件x+k-1<=a且y+k-1<=b（保证正方形不超出操场的范围）。

2. 对于每个左上角位置(x,y)，计算右下角位置(x2,y2)：x2=x+k-1，y2=y+k-1。

3. 计算以(x2,y2)为右下角的正方形区域内的红色砖块的数量d：

d = sum[x2][y2] - sum[x-1][y2] - sum[x2][y-1] + sum[x-1][y-1]

4. 如果d等于0或者等于k*k（即整个区域内都是红色砖块或者蓝色砖块），则找到了一个满足条件的正方形，输出其面积k*k。

5. 如果没有找到满足条件的正方形，继续递减正方形大小k，重复步骤2-4。

最后，如果没有找到任何满足条件的正方形，则输出0。

C++代码实现：

#include<bits/stdc++.h>
using namespace std;
long long a,b,e[1000][1000],sum[1000][1000];
int main()
{
    cin>>a>>b;
    for(long long i=1;i<=a;i++)
    {
        for(int j=1;j<=b;j++)
        {
            cin>>e[i][j];
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+e[i][j];
        }
    }
    long long n=min(a,b);
    for(int k=n;k>=1;k--)
    {
        for(int x=1;x+k-1<=a;x++)
        {
            for(int y=1;y+k-1<=b;y++)
            {
                long long x2=x+k-1;
                long long y2=y+k-1;
                long long d=sum[x2][y2]-sum[x-1][y2]-sum[x2][y-1]+sum[x-1][y-1];
                if(d==0||d==k*k)
                {
                    cout<<k*k;
                    return 0;
                }
            }
        }
    }
    
    cout<<0;
    return 0;
}

这样就可以找到最大纯色正方形的面积了。

点个赞吧，帅哥美女们，本人为小学生。

原文地址：https://blog.csdn.net/gcliyilin/article/details/143469590

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！