【蓝桥杯】ALGO-112 暗恋
- 2019 年 11 月 13 日
- 筆記
版权声明：本文为博主原创文章，遵循 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; }
