最大矩阵面积问题_最大的空矩形面积 数据随机 平衡树

问题概述

最大矩阵面积问题有两种：

1. 在一个网格图中，一些格子里有障碍，求在网格图中规划一个矩形，使得它不会覆盖任何一个障碍格且面积最大。
2. 在一个平面直角坐标系中，先给你规定一个大矩形（一般左下角是 $(0,0)$，右上角是 $(MaxX,MaxY)$），有一些障碍点，求在这个大矩形中规划一个小矩形，使得它不会覆盖每一个障碍点（障碍点可在矩形边缘）。

具体问题

对于第一个类型：洛谷 P4147 玉蟾宫
对于第二个类型：洛谷 P1578 奶牛浴场

解法

1.悬线法

一般用在方格图中，时间复杂度为整个方格图大小 $O(nm)$。
设 h i , j h_{i,j} hi,j​ 表示从 $(i,j)$ 出发，向上拓展，成一个左右宽度为一格的细长矩形的高度。
如下图：
（学校机房图片上传不上去，先鸽着）

再设 l i , j ,  r i , j l_{i, j},\\space r_{i, j} li,j​, ri,j​ 为以这个细长矩形为中轴线，向左、向右拓展，遇到第一个障碍格的列坐标（没有的话就分别设为 $0$ 和 $m+1$）。
如下图：
（同上）

枚举每个格子，求出每个 h i , j , l i , j , r i , j h_{i,j},l_{i,j},r_{i,j} hi,j​,li,j​,ri,j​ 的值，最后用 h i , j ×( r i , j −1− l i , j ) h_{i,j} \\times (r_{i, j} - 1 - l_{i,j}) hi,j​×(ri,j​−1−li,j​) 来更新最大面积 $ans$。

下面给出玉蟾宫代码：

#include using namespace std;const int maxn = 1e3 + 7;int n, m, ans = 1;char g[maxn][maxn];// l[i][j]:(i, j)向左能到达最远的地方// r[i][j]:(i, j)向右能到达最远的地方// h[i][j]:(i, j)向上能到达最远的地方// ans = max(ans, (r[i][j] - l[i][j] + 1) * h[i][j])// 看看是不是全是 Rbool check() {for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (g[i][j] != \'R\') return false;return true;}int l[maxn][maxn], r[maxn][maxn], h[maxn][maxn];int main() { scanf(\"%d%d\", &n, &m);for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> g[i][j];h[i][j] = 1, l[i][j] = r[i][j] = j;}for (int j = 2; j <= m; j++) if (g[i][j - 1] == \'F\' && g[i][j] == \'F\') l[i][j] = l[i][j - 1];for (int j = m - 1; j >= 1; j--) if (g[i][j + 1] == \'F\' && g[i][j] == \'F\') r[i][j] = r[i][j + 1];}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (g[i][j] == \'F\' && g[i - 1][j] == \'F\' && i > 1) {h[i][j] = h[i - 1][j] + 1;if (l[i - 1][j] > l[i][j]) l[i][j] = l[i - 1][j];if (r[i - 1][j] < r[i][j]) r[i][j] = r[i - 1][j]; /* R F RF F F (2, 2)为当前所在位置，l[2][2]原本等于1, r[2][2]原本等于3, 但由于g[1][2] == \'F\', 符合 h 更新要求,所以l[2][2]更新为2, r[2][2]更新为2. */}ans = max(ans, (r[i][j] - l[i][j] + 1) * h[i][j]); /* 当l[2][2] == 2, r[2][2] == 2, h[2][2] == 2时,答案显然不是最优, 当循环扫到(2, 1)时,l[2][1] == 1, r[2][1] == 3, h[2][1] == 1,答案最优. */}}// 特判是否全为 R if (check())printf(\"0\\n\");else printf(\"%d\\n\", ans * 3);return 0;}

当然还可以用单调站求 h i , j , l i , j , r i , j h_{i,j},l_{i,j},r_{i,j} hi,j​,li,j​,ri,j​ ：

#include using namespace std;typedef long long ll;const int maxn = 1e3 + 7;const int inf = 0x3f3f3f3f;int n, m;bool a[maxn][maxn];int h[maxn][maxn];int l[maxn][maxn], r[maxn][maxn];int sta[maxn], top;int ans;int main() { scanf(\"%d%d\", &n, &m); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) { char c; cin >> c; a[i][j] = (c == \'F\');} for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) if (a[i][j]) h[i][j] = h[i - 1][j] + 1; top = 0;for (int j = 1; j <= m; ++j) {while (top > 0 && h[i][sta[top]] > h[i][j]) {r[i][sta[top]] = j;--top;}sta[++top] = j;}while (top > 0) {r[i][sta[top]] = m + 1;--top;}top = 0;for (int j = m; j >= 1; --j) {while (top > 0 && h[i][sta[top]] > h[i][j]) {l[i][sta[top]] = j;--top;}sta[++top] = j;}while (top > 0) {l[i][sta[top]] = 0;--top;}for (int j = 1; j <= m; ++j) ans = max(ans, h[i][j] * (r[i][j] - 1 - l[i][j]));}// 这个不用特判// 因为若全是 R, 每一个 h[i][j] 都为 0printf(\"%d\\n\", ans * 3);return 0;} 

2.障碍点法

一般用在平面直角坐标系中，时间复杂度与障碍点个数有关，为 O( n 2 ) O(n^2) O(n2)。
可以看看这篇题解。

#include #define mkpr make_pairusing namespace std;typedef long long ll;typedef pair<int, int> pii;const int maxn = 5e3 + 7;int L, W, n;struct point { int x, y; point() {} point(int _x, int _y) : x(_x), y(_y) {}} p[maxn];bool cmp1(point a, point b) {return a.x < b.x;}bool cmp2(point a, point b) {return a.y < b.y;}int ans;int main() { scanf(\"%d%d%d\", &L, &W, &n); for (int i = 1; i <= n; ++i) scanf(\"%d%d\", &p[i].x, &p[i].y); p[++n] = point(0, 0), p[++n] = point(L, 0); p[++n] = point(0, W), p[++n] = point(L, W); sort(p + 1, p + n + 1, cmp1); // 从左往右扫  for (int i = 1; i <= n; ++i) { int up = W, down = 0; for (int j = i; j <= n; ++j) { while (p[i].x == p[j].x && j <= n) ++j; if (j > n) break; ans = max(ans, (up - down) * (p[j].x - p[i].x)); if (p[i].y <= p[j].y) up = min(up, p[j].y); if (p[i].y > p[j].y) down = max(down, p[j].y);}} // 从右往左扫 for (int i = n; i >= 1; --i) { int up = W, down = 0; for (int j = i; j >= 1; --j) { while (p[i].x == p[j].x && j >= 1) --j; if (j < 1) break; ans = max(ans, (up - down) * (p[i].x - p[j].x)); if (p[i].y <= p[j].y) up = min(up, p[j].y); if (p[i].y > p[j].y) down = max(down, p[j].y); } } sort(p + 1, p + n + 1, cmp2); // 特殊情况：小矩形左右边与大矩形左右边重合  for (int i = 1; i <= n - 1; ++i) ans = max(ans, L * (p[i + 1].y - p[i].y)); printf(\"%d\\n\", ans);return 0;}

深圳旅游景点大全