首先把矩阵转化一下,把横纵坐标和为偶数点的值取反,这样就转化成求最大的'0'或'1'矩阵。

这道题每个数字是在格子内的,不能在边界包含障碍点。

求最大的0矩阵时,把1作为障碍点。求1同理。

然后求最接近的就可以用树状数组求解啦~

 #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; const int N=,Inf=(int)1e9;
int n,m,a1,a2;
int a[N][N],l[N][N],r[N][N],last[N][N],cl[N][N],cr[N][N]; int minn(int x,int y){return x<y ? x:y;}
int maxx(int x,int y){return x>y ? x:y;} void add(int x,int y,int d)
{
for(int i=y;i<=m;i+=(i&(-i))) cl[x][i]=maxx(cl[x][i],d);
for(int i=y;i>=;i-=(i&(-i))) cr[x][i]=minn(cr[x][i],d);
} int get(int x,int y,int tmp)
{
if(tmp==)
{
int ans=;
for(int i=y-;i>=;i-=(i&(-i))) ans=maxx(ans,cl[x][i]);
if(ans==) return ;
else return ans+;
}
else
{
int ans=Inf;
for(int i=y+;i<=m;i+=(i&(-i))) ans=minn(ans,cr[x][i]);
if(ans>=Inf) return m;
else return ans-;
}
} void solve(int tmp)
{
memset(cl,,sizeof(cl));
memset(cr,,sizeof(cr));
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
if(a[i][j]==tmp) add(i,j,j);
}
memset(l[],,sizeof(l[]));
memset(r[],,sizeof(r[]));
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(a[i][j]==tmp) continue;
if(a[i-][j]==tmp)
{
l[i][j]=get(i,j,);//debug
r[i][j]=get(i,j,);//debug
last[i][j]=i-;
}
else
{
l[i][j]=maxx(l[i-][j],get(i,j,));
r[i][j]=minn(r[i-][j],get(i,j,));
last[i][j]=last[i-][j];
}
int xx=r[i][j]-l[i][j]+;
int yy=i-last[i][j];
a1=maxx(a1,minn(xx,yy)*minn(xx,yy));
a2=maxx(a2,xx*yy);
}
}
} int main()
{
freopen("a.in","r",stdin);
scanf("%d%d",&n,&m);
a1=;a2=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&a[i][j]);
if((i+j)%==) a[i][j]^=;
}
solve();
solve();
printf("%d\n%d\n",a1,a2);
return ;
}

最新文章

  1. js 获取鼠标选中值
  2. 在yii框架中如何连接数据库mongodb
  3. tmux常用命令
  4. LeetCode Alien Dictionary
  5. [转载]在线文档预览方案-Office Web Apps
  6. os模块
  7. JavaWeb学习总结(一)—JavaWeb开发入门及环境搭建
  8. XML HTML
  9. Differential Geometry之第二章曲线的局部理论
  10. JavaScript---网络编程(4)-Date、Math、Global和自定义对象
  11. flushall()函数的用法
  12. opencv中Mat类型数据操作与遍历
  13. ArcGis ToolBar为灰色
  14. 2017寒假零基础学习Python系列之 印子
  15. +function ($) { &quot;use strict&quot;;}(window.jQuery);全面分析
  16. linux常用命令及使用技巧(二)
  17. appium自动化测试 环境搭建
  18. 【struts2】&lt;package&gt;的配置
  19. ASP.NET Core 如何设置发布环境
  20. linux任务计划cron

热门文章

  1. laravel+vue结合使用
  2. nginx location优先级
  3. Android 序列化比对
  4. Python-类-函数参数-takes 0 positional arguments but 1 was given
  5. 【LoadRunner】解决LR11无法录制Chrome浏览器脚本问题
  6. EM算法浅析(二)-算法初探
  7. AMF3 在Unity中使用AMF3和Java服务器通信
  8. Java 8手动实现一个Collector
  9. c# dll使用注意
  10. 利用calibre抓取新闻