蓝桥杯 ALGO-112 VIP试题暗恋（试题解析）_综合

试题算法训练暗恋

提交此题评测记录

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

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

输入格式

　　第一行两个正整数R和C。
　　接下来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

样例输出

数据规模和约定

　　40%的数据R,C<=10;
　　70%的数据R,C<=50;
　　100%的数据R,C<=200;

解题思路：找面积最大的纯色正方形，用搜素法，以坐标（i,j）为基点，边长为S,不断遍历搜索。当然，简单朴素的搜索最终肯定会超时，所以，我们要加入可行性剪枝2： S>sqrt(lvSd) （前面的可行性剪枝1 貌似没有什么效果。。。），若当前的边长S大于目前的面积最大的纯色正方形的边长，则继续遍历；否则，跳过。。。。最后就AC了。

代码如下：

#include <iostream>
#include <string.h>
#include <cmath>
using namespace std;

int G[210][210];
int R,C;
int lvSd=1;
int check[210][210];   //检查方格砖（i,j）是否与其左边的砖同色。 0表示同色，1表示不同

void Read(){
   cin>>R>>C;

   for(int i=1;i<=R;i++){
       for(int j=1;j<=C;j++){
           cin>>G[i][j];
       }
   }

   for(int i=1;i<=R-1;i++){
       for(int j=1;j<=C-1;j++){
           if(G[i][j]!=G[i][j+1] || G[i][j]!=G[i+1][j] )
               check[i][j]=1;
       }
   }

}

int getArea(int x,int y,int S){

   bool isPure=true;
   int first=G[x][y];
   for(int i=x;i<=x+S-1;i++){
       for(int j=y;j<=y+S-1;j++){
           if(G[i][j]!=first){
               isPure=false;
               break;
           }
       }
   }

   if(isPure)
       return S*S;
   else
       return 0;

}

void FindLoveStandard(){

   for(int i=1;i<=R;i++){
       for(int j=1;j<=C;j++){
           if( check[i][j]==0 ){// 可行性剪枝1
               for(int S=1;i+S-1<=R && j+S-1<=C;S++ ){
                   if( S>sqrt(lvSd) )   // 可行性剪枝2
                       lvSd=max(lvSd,getArea(i,j,S));
               }
           }
       }
   }
   cout<<lvSd<<endl;
}

int main(int argc, char** argv) {
Read();
FindLoveStandard();

return 0;
}

蓝桥杯 ALGO-112 VIP试题 暗恋 （试题解析）

试题 算法训练 暗恋

蓝桥杯 ALGO-112 VIP试题暗恋（试题解析）

试题算法训练暗恋