题意:

  给出点(x1,y1),求以x=x1为上边界,或下边界;以y=y1为左边界,或右边界矩形的最大值(矩形内所有的点均为1)

定义四个数组lft[][],rht[][],up[][],down[][]

在up[x][y]中存的是

点(x,y)的上边有多少个连续的1

其他同理;

在确定最大的矩形时,用到了枚举法,go函数;

代码参考自:vjudge2

代码风格:思路清晰,代码明了

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAX = ;
bool ma[MAX][MAX];
int lft[MAX][MAX],rht[MAX][MAX],up[MAX][MAX],down[MAX][MAX];
int len[MAX];
int rows,cols,q; void upd_row(int x)
{
for(int j=; j<=cols; j++)
{
if(ma[x][j])
lft[x][j] = lft[x][j-]+;
else lft[x][j]=;
}
for(int j=cols; j>=; j--)
{
if(ma[x][j])
rht[x][j]=rht[x][j+]+;
else rht[x][j] =;
}
}
void upd_col(int y)
{
for(int i=; i<=rows; i++)
{
if(ma[i][y])
up[i][y] = +up[i-][y];
else up[i][y] = ;
}
for(int i=rows; i>=; i--)
{
if(ma[i][y])
down[i][y]=+down[i+][y];
else down[i][y]=;
}
} int go(int tmp,int n)
{
int leftmost = tmp;
int rightmost = tmp;
int ret = ;
for(int final = len[tmp]; final >=; final--)
{
while(leftmost>= && final<=len[leftmost])
--leftmost;
while(rightmost<=n && final<=len[rightmost])
++rightmost;
ret = max(ret,final*(rightmost-leftmost-));
}
return ret;
}
int main()
{
int i,j;
int op,x,y;
int ans;
while(scanf("%d %d %d",&rows,&cols,&q)!=EOF)
{
for(i=; i<=rows; i++)
for(j=; j<=cols; j++)
scanf("%d",&ma[i][j]);
for(i=; i<=rows; i++)
upd_row(i);
for(j=; j<=cols; j++)
upd_col(j);
while(q--)
{
scanf("%d %d %d",&op,&x,&y);
if(op==)
{
ma[x][y]=!ma[x][y];
//for(i=1; i<=rows; i++)
upd_row(x);
//for(j=1; j<=cols; j++)
upd_col(y);
}
else
{
ans=;
for(i=; i<=rows; i++)len[i]=lft[i][y];
ans=max(ans,go(x,rows));
for(i=; i<=rows; i++)len[i]=rht[i][y];
ans=max(ans,go(x,rows));
for(j=; j<=cols; j++)len[j]=down[x][j];
ans=max(ans,go(y,cols));
for(j=; j<=cols; j++)len[j]=up[x][j];
ans=max(ans,go(y,cols));
printf("%d\n",ans);
}
}
}
return ;
}

最新文章

  1. MySQL MHA 搭建&amp;测试
  2. (转)android中颜色矩阵colormatrix
  3. myeclipse自动import
  4. java笔记--查看和修改线程名称
  5. 如何实现一个malloc
  6. oracle:触发器,自治事务 trigger
  7. sizeof对int long double char的使用
  8. elasticsearch使用river同步mysql数据
  9. IQKeyboardManager 状态栏(status bar)问题
  10. HTML篇(下&#183;)
  11. 分布式锁的几种使用方式(redis、zookeeper、数据库)
  12. .NETCore 千星项目模块化开发框架 SimplCommerce 详解
  13. Python爬虫(2):urllib库
  14. gdbserver移植到DM368板子上的过程 以及segment fault problem
  15. Flask+Nginx+Supervisor+Gunicorn+HTTPS部署教程(CentOs)
  16. nexus的jar包上传与下载
  17. 包建强的培训课程(6):Android App瘦身优化
  18. js日期
  19. es定制排序搜索结果
  20. 转:使用 python Matplotlib 库 绘图 及 相关问题

热门文章

  1. 【java规则引擎】drools6.5.0版本中kmodule.xml解析
  2. 转 OpenFaaS 介绍
  3. Go入门教程
  4. 关于app集成支付宝应用内支付的问题总结
  5. COGS 2259 异化多肽——生成函数+多项式求逆
  6. 【Python学习笔记】输出现在的时间
  7. android中MediaPlayer类的用法
  8. sonar 获取扫描结果(二)
  9. iPhone之IOS5内存管理(ARC技术概述)
  10. 使用wireshark观察SSL/TLS握手过程--双向认证/单向认证