【蓝桥杯】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;
}
C++
Copy