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