【蓝桥杯】ALGO-112 暗恋
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/weixin_42449444/article/details/102994124
题目描述：
同在一个高中，他却不敢去找她，虽然在别人看 来，那是再简单不过的事。暗恋，是他唯一能做的事。他只能在每天课间操的时候，望望她的位置，看看她倾心的动作，就够了。操场上的彩砖啊，你们的位置，就是他们能够站立的地方，他俩的关系就像砖与砖之间一样固定，无法动摇。还记得当初铺砖的工人，将整个操场按正方形铺砖（整个操场可视为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;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-11-10 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录