传送门

总之可以先预处理出来每个位置最多往上延伸多少

枚举两行,看看夹在这两行中间的列最大能构成多大的矩形

可以看出,必须得在一个两行都没有X的区间才有可能构成最大的答案

那么可以把这些区间处理出来,在看看这些区间中的点最左边和最右边的能从下面那一行向上延伸到上面那一行的点,更新ans即可

#include <cstdio>
#define N 201
#define max(x, y) ((x) > (y) ? (x) : (y)) int n, m, ans, p;
int h[N][N], b[N];
char s[N][N]; int main()
{
int i, j, k;
scanf("%d %d", &n, &m);
for(i = 1; i <= n; i++)
{
scanf("%s", s[i] + 1);
for(j = 1; j <= m; j++)
if(s[i][j] == '.')
h[i][j] = h[i - 1][j] + 1;
}
for(i = 1; i <= n; i++)
for(j = i + 1; j <= n; j++)
{
p = -1;
for(k = 1; k <= m; k++) b[k] = h[j][k];
for(k = 1; k <= m; k++)
if(s[i][k] == 'X')
b[k] = 0;
for(k = 1; k <= m; k++)
{
if(!b[k]) p = -1;
if(j - b[k] < i && p == -1) p = k;
if(j - b[k] < i && p != -1) ans = max(ans, (k - p + 1) * (j - i + 1));
}
}
printf("%d\n", ans);
return 0;
}

  

最新文章

  1. jekins 持续集成手记
  2. JS设置cookie、读取cookie、删除cookie
  3. hadoop fs 命令
  4. spring ehcache 页面、对象缓存
  5. 安装DotNetCore.1.0.0-VS2015Tools.Preview2失败解决方案
  6. ajax读取json数据
  7. 一个inline-block的样式。
  8. 【C#学习笔记】Dictionary容器使用
  9. [oracle]一个最简单的oracle存储过程&quot;proc_helloworld&quot;
  10. Android Gson使用笔记
  11. Failed to issue method call: Unit mysql.service failed to load: No such file or directory解决的方式
  12. Health Check in eShop -- 解析微软微服务架构Demo(五)
  13. Tp3.2提交表单与操作表单
  14. CSS继承、层叠和特殊性
  15. 在windows8.1下安装ubuntu16.04
  16. Apollo源码阅读笔记(一)
  17. 【入门推荐】SQL注入进行WebShell渗透测试的基础概览
  18. 3.23日PSP
  19. Oracle数据库备份还原工具之Expdp/IMPdp
  20. 【POJ1284】Primitive Roots

热门文章

  1. Spring Boot :Druid Monitor
  2. 【page-monitor 前端自动化 上篇】初步调研
  3. CPP-基础:strcpy之于C++(
  4. shell脚本,计算输入给定的数,判断最大值,最小值,总和?
  5. ios之UITabelViewCell的自定义(xib实现2)
  6. 167. Two Sum II - Input array is sorted@python
  7. Codeforces Round #510 #B
  8. OJ 大整数减法
  9. 组合的输出(DFS)
  10. 初涉KMP算法