给一个01矩阵,求面积最大的只含有1的子矩形和正方形
定义
对于一个包含障碍的矩阵,从一个点出发向四周能扩展到的最大的矩形称为极大子矩形,显然极大子矩形的四条边上都至少有一个障碍物.所有极大子矩形中面积最大的成为最大子矩形.
最大子正方形
只是求最大子正方形可以设计一个DP解法
设dp(x,y)为以(x,y)为右下角的最大正方形
dp(x,y) = min(dp(x - 1,y) , dp(x,y - 1) , dp(x - 1,y - 1)) + 1
但是DP解法无法处理最大子矩形,因此需要悬线法
悬线法
悬线法是一个求极大子矩形的算法
操作方式
对于一个点(x,y) ,从此处向上划一条线直到碰到障碍,记长度为d(x,y),接着将该线向左,向右扫描,直到碰到障碍
注意: 这个扫描得到的矩形未必是极大子矩形,因为其下边界未必触及障碍.但它随后一定会成为一个极大子矩形的子矩形,不会出现遗漏
以上操作进一步抽象如下:
对第x行的数列d(x),求每一个元素d(x,y)作为前缀最小值和后缀最小值时最长的子列长度right(x,y),left(x,y).该矩形面积为
d(x,y) * (right(x,y) + left(x,y) - 1)
d(x,y)的维护可以通过动态规划实现,维护复杂度为O(1),同时可以使用滚动数组优化.
那么如何实现平均O(1)维护后缀最小值数组?
后缀最小值
对于点(x,y),朴素维护其后缀最小值数组即询问它之前的每一个元素即d(x,y - k),0 < k <= y是否小于d(x,y) . 复杂度高达O(n)
注意:若一个元素d(x,j) <= d(x,y),则显而易见(x,j)的后缀最小值数组一定能成为(x,y)的后缀最小值数组的一部分,可以直接跳过这一段的询问.若d(x,j) > d(x,y),则询问到此为止,无需向前询问.
由此可以得到两个结论:
- 所有询问中每个元素只需肯定回答一次
- 每个元素发出的询问只会得到一个否定回答
询问次数最多为2*n,时间复杂度为O(1)
相关题目
USACO5.3巨大的牛棚
农夫约翰想要在他的正方形农场上建造一座正方形大牛棚。他讨厌在他的农场中砍树，想找一个能够让他在空旷无树的地方修建牛棚的地方。我们假定，他的农场划分成 N x N 的方格。输入数据中包括有树的方格的列表。你的任务是计算并输出，在他的农场中，不需要砍树却能够修建的最大正方形牛棚。牛棚的边必须和水平轴或者垂直轴平行。
EXAMPLE
考虑下面的方格，它表示农夫约翰的农场，‘.’表示没有树的方格，‘#’表示有树的方格
1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . # . . . # . .
3 . . . . . . . .
4 . . . . . . . .
5 . . . . . . . .
6 . . # . . . . .
7 . . . . . . . .
8 . . . . . . . .
最大的牛棚是 5 x 5 的，可以建造在方格右下角的两个位置其中一个。
ZJOI2007棋盘制作
国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个 8×8 大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。
而我们的主人公
小Q，正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规则，于是他跟他的好朋友小W决定将棋盘扩大以适应他们的新规则。
小Q找到了一张由 N×M 个正方形的格子组成的矩形纸片，每个格子被涂有黑白两种颜色之一。小Q想在这种纸中裁减一部分作为新棋盘，当然，他希望这个棋盘尽可能的大。不过
小Q还没有决定是找一个正方形的棋盘还是一个矩形的棋盘（当然，不管哪种，棋盘必须都黑白相间，即相邻的格子不同色），所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积，从而决定哪个更好一些。于是
小Q找到了即将参加全国信息学竞赛的你，你能帮助他么？
for (int i = 1;i <= n;++ i){
for (int j = 1;j <= m;++ j){
dp[j] = (dp[j] + 1 ) * map_[i][j];//map_表示输入地图
if(!dp[j]){
l[j] = 0;
continue;
}
int k = j - 1;
while (dp[k] >= dp[j])
k = k - l[k];
l[j] = j - k;
}
for (int j = m;j >= 1;-- j){
if(!dp[j]){
r[j] = 0;
continue;
}
int k = j + 1;
while (dp[k] >= dp[j])
k = k + r[k];
r[j] = k - j;
ans1 = max(ans1,min(r[j] + l[j] - 1,dp[j]));//正方形
ans2 = max(ans2,(r[j] + l[j] - 1) * dp[j]);//矩形
}
}