懸線法求解最大矩型

10-16

懸線法求解最大矩型

懸線法用來求解最大子矩形問題

最大子矩形問題

在一個給定的矩形中有一些障礙點，找出內部不包含障礙點的，邊與整個矩形平行或重合的最大子矩形。

定義

有效子矩型：滿足要求的子矩形
極大子矩型：無法再向外拓展的有效子矩形
最大子矩型：最大的一個有效子矩形
須知：在一個有障礙點的矩形中，最大子矩形一定是極大子矩形

解決方案

【演算法1】

枚舉，極大子矩形沒一條邊都無法向外拓展，故而其邊有兩種情況

邊覆蓋障礙點
邊與矩形邊緣重合

由此可以枚舉上下左右四個邊界，然後判斷組成的舉行是否是有效子矩陣，由此求出問題答案

複雜度： $O(s^5)$ （s為障礙點數）

這個演算法實現過程中產生了大量的非有效子矩陣，如果可以避免產生這些矩陣，可以大大減慢複雜度。可以通過枚舉左右邊界，然後神奇操作一下將時間複雜度降到 $O(s^2)$

應用於點較稀疏的時候

【演算法2】

懸線法

定義

有效豎線：除了兩個端點以外，不覆蓋任何一個障礙點的豎直線段
懸線：上端覆蓋了一個障礙點或者到達整個矩形上邊界的有效線段

每個懸線上的點的與底部的點一一對應，矩形中每一個點（矩形頂部點除外）都對應了一條懸線。

如果把一條懸線向左右兩個方向儘可能的移動，那麼就得到了一個矩形。

注意：懸線對應的矩型不一定是極大子矩陣，因為懸線定義中固定了懸線的下邊界，故而，懸線左右移動所得到的矩形無法向下擴展。

有以下定義

$height_{i, j}$ ：表示以 $(i,j)$ 為底的懸線的高
$left_{i,j}$ ：表示向左最多能移動到的位置
$right_{i,j}$ ：表示向右最多能移動到的位置

初始化定義為以下

$egin{cases} height_{i,j}&=&1\ left_{i,j}&=&0\ right_{i,j}&=&m end{cases}$

考慮懸線長度

如果點 $(i-1, j)$ 不是障礙點，那麼，以 $(i,j)$ 為底的懸線就等於以 $(i-1,j)$ 為底的懸線加點 $(i,j)$ 到點 $(i - 1,j)$ 的線段。因此， $height_{i,j}=height_{i-1,j}+1$ 。

考慮左右能移動的最大位置

因為懸線長度的更新，所以要更新左右能到達的位置

該圖表示更新left值

得到遞推式

$egin{cases} height_{i,j}&=&height_{i,j}+1\ left_{i,j}&=&maxegin{cases}left_{i-1,j}\(i-1,j)右邊第一個障礙點位置 end{cases}\ right_{i,j}&=&minegin{cases}right_{i-1,j}\(i-1,j)右邊第一個障礙點位置end{cases} end{cases}$

注意，障礙點包括左右邊界（即 $0,m$ ）

這樣，每個懸線處理時間複雜度為 $O(1)$ 。

對於以點 $(i, j)$ 為底的懸線對應的子矩形，其面積計算為

${(right_{i,j}-left_{i,j}) imes height_{i,j}}$

問題解： $ans = max egin{cases} (right_{i,j}-left_{i,j})*height_{i,j} end{cases}$

時間複雜度： $O(nm)$ ；空間複雜度： $O(nm)$

這一種方法適用於點較密集的時候

推薦題目

【P1169】[ZJOI2007]棋盤製作 - 洛谷?

www.luogu.org

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>const int maxn = 4001;int n, m, ans1, ans2;int res[maxn][maxn], left[maxn][maxn], right[maxn][maxn], height[maxn][maxn];int main(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) { scanf("%d", &res[i][j]); left[i][j] = right[i][j] = j; height[i][j] = 1; } for (int i = 1; i <= n; ++i) for (int j = 2; j <= m; ++j) if (res[i][j] != res[i][j - 1]) left[i][j] = left[i][j - 1]; for (int i = 1; i <= n; ++i) for (int j = m - 1; j > 0; --j) if (res[i][j] != res[i][j + 1]) right[i][j] = right[i][j + 1]; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) { if (i > 1 && res[i][j] != res[i - 1][j]) { left[i][j] = std::max(left[i][j], left[i - 1][j]); right[i][j] = std::min(right[i][j], right[i - 1][j]); height[i][j] = height[i - 1][j] + 1; } int a = right[i][j] - left[i][j] + 1; int b = std::min(a, height[i][j]); ans1 = std::max(ans1, b * b); ans2 = std::max(ans2, a * height[i][j]); } printf("%d %d", ans1, ans2); return 0;}

參考文獻

王知昆：淺談用極大化思想解決最大子矩形問題