最大矩阵面积问题

问题概述

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

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

具体问题

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

解法

1.悬线法

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

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

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

下面给出玉蟾宫代码：

#include <bits/stdc++.h>
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])

// 看看是不是全是 R
bool 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 R
				F 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}$ ：

#include <bits/stdc++.h>

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] 都为 0
	printf("%d\n", ans * 3);
	return 0;
} 

2.障碍点法

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

#include <bits/stdc++.h>

#define mkpr make_pair

using 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;
}