【蓝桥杯】ALGO-112 暗恋

正文索引 [隐藏]

题目描述:

同在一个高中,他却不敢去找她,虽然在别人看  来,那是再简单不过的事。暗恋,是他唯一能做的事。他只能在每天课间操的时候,望望她的位置,看看她倾心的动作,就够了。操场上的彩砖啊,你们的位置,就是他们能够站立的地方,他俩的关系就像砖与砖之间一样固定,无法动摇。还记得当初铺砖的工人,将整个操场按正方形铺砖(整个操场可视为R行C列的矩阵,矩阵的每个元素为一块正方形砖块),正方形砖块有两种,一种为蓝色,另一种为红色。我们定义他和她之间的“爱情指标”为最大纯色正方形的面积,请你写一个程  序求出“爱情指标”。

输入描述:

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

输出描述:

一个数,表示他和她之间的“爱情指标”。

输入样例:

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

输出样例:

9

解题思路:

暴力破解,从输入矩阵左上⻆的点开始枚举,依次向右下角探测最大正方形的⾯积,不断更新最大值ans,最后进行输出即可。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)
#define ms(a,x) memset(a,x,sizeof(a))
const int maxn = 201;
const int INF = 0x3f3f3f3f;

int a[maxn][maxn];

int check(int x,int y)  //寻找从(x,y)开始向右下角探测的最大正方形的面积
{
    Up(i,1,maxn)
    {
        Up(j,x,x+i)
        {
            if(a[j][y+i] != a[x][y]) return i*i;
        }
        Up(j,y,y+i)
        {
            if(a[x+i][j] != a[x][y]) return i*i;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    ms(a,INF);
    int r,c;    //rhangc列
    cin >> r >> c;
    Up(i,1,r)
    {
        Up(j,1,c)
        {
            cin >> a[i][j];
        }
    }
    int ans = 0;
    Up(i,1,r)
    {
        Up(j,1,c)
        {
            ans = max(ans,check(i,j));
        }
    }
    cout << ans << endl;
    return 0;
}