拼图：查找最大矩形（最大矩形问题）
什么是最有效的算法来找到最大的区域将适合在空的空间矩形？
假设屏幕看起来像这样（'＃'代表填充区域）：
....................
..............######
##..................
.................###
.................###
#####...............
#####...............
#####...............
一个可能的解决方案是：
....................
..............######
##...++++++++++++...
.....++++++++++++###
.....++++++++++++###
#####++++++++++++...
#####++++++++++++...
#####++++++++++++...
通常我会喜欢搞清楚解决方案。 虽然这次我想避免浪费时间在我自己身上摸索，因为这对我正在开发的项目有实际的用处。 有没有一个众所周知的解决方案？
Shog9写道：
你的输入是一个数组（如其他响应所暗示的），还是任意大小的定位矩形形式的遮挡列表（当处理窗口位置时可能出现在窗口系统中）？
是的，我有一个跟踪放置在屏幕上的一组窗口的结构。 我还有一个网格，用于跟踪每条边之间的所有区域，无论它们是空的还是已填满的，以及左边或上边的像素位置。 我认为有一些修改后的表格可以利用这个属性。 你知道吗？
@lassevk
我发现DDJ引用的文章：最大矩形问题
我是Dobb博士文章的作者，偶尔会询问有关实施的问题。 这里是一个简单的C：
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int one;
int two;
} Pair;
Pair best_ll = { 0, 0 };
Pair best_ur = { -1, -1 };
int best_area = 0;
int *c; /* Cache */
Pair *s; /* Stack */
int top = 0; /* Top of stack */
void push(int a, int b) {
s[top].one = a;
s[top].two = b;
++top;
}
void pop(int *a, int *b) {
--top;
*a = s[top].one;
*b = s[top].two;
}
int M, N; /* Dimension of input; M is length of a row. */
void update_cache() {
int m;
char b;
for (m = 0; m!=M; ++m) {
scanf(" %c", &b);
fprintf(stderr, " %c", b);
if (b=='0') {
c[m] = 0;
} else { ++c[m]; }
}
fprintf(stderr, "n");
}
int main() {
int m, n;
scanf("%d %d", &M, &N);
fprintf(stderr, "Reading %dx%d array (1 row == %d elements)n", M, N, M);
c = (int*)malloc((M+1)*sizeof(int));
s = (Pair*)malloc((M+1)*sizeof(Pair));
for (m = 0; m!=M+1; ++m) { c[m] = s[m].one = s[m].two = 0; }
/* Main algorithm: */
for (n = 0; n!=N; ++n) {
int open_width = 0;
update_cache();
for (m = 0; m!=M+1; ++m) {
if (c[m]>open_width) { /* Open new rectangle? */
push(m, open_width);
open_width = c[m];
} else /* "else" optional here */
if (c[m]<open_width) { /* Close rectangle(s)? */
int m0, w0, area;
do {
pop(&m0, &w0);
area = open_width*(m-m0);
if (area>best_area) {
best_area = area;
best_ll.one = m0; best_ll.two = n;
best_ur.one = m-1; best_ur.two = n-open_width+1;
}
open_width = w0;
} while (c[m]<open_width);
open_width = c[m];
if (open_width!=0) {
push(m0, w0);
}
}
}
}
fprintf(stderr, "The maximal rectangle has area %d.n", best_area);
fprintf(stderr, "Location: [col=%d, row=%d] to [col=%d, row=%d]n",
best_ll.one+1, best_ll.two+1, best_ur.one+1, best_ur.two+1);
return 0;
}
它从控制台获取输入。 你可以例如管这个文件给它：
16 12
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 0
0 0 0 1 1 0 1 1 1 0 1 1 1 0 1 0
0 0 0 0 1 1 * * * * * * 0 0 1 0
0 0 0 0 0 0 * * * * * * 0 0 1 0
0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 0
0 0 1 0 0 0 0 1 0 0 1 1 1 0 1 0
0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0
打印输入后，它会输出：
The maximal rectangle has area 12.
Location: [col=7, row=6] to [col=12, row=5]
上面的实现当然没什么特别，但它非常接近Dobb博士文章中的解释，应该很容易翻译成任何需要的东西。
这是一个包含一些代码和一些分析的页面。
您的特定问题在页面上开始一点点，搜索文本最大矩形问题的页面。
http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module6/module6.html
链接地址: http://www.djcxy.com/p/94603.html上一篇: Puzzle: Find largest rectangle (maximal rectangle problem)