- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
找到适合空白空间的面积最大的矩形的最有效算法是什么?
假设屏幕看起来像这样('#' 代表填充区域):
....................
..............######
##..................
.................###
.................###
#####...............
#####...............
#####...............
一个可能的解决方案是:
....................
..............######
##...++++++++++++...
.....++++++++++++###
.....++++++++++++###
#####++++++++++++...
#####++++++++++++...
#####++++++++++++...
通常我会很乐意找出解决方案。虽然这次我想避免浪费时间自己摸索,因为这对我正在从事的项目有实际用途。是否有众所周知的解决方案?
Shog9 写道:
Is your input an array (as implied by the other responses), or a list of occlusions in the form of arbitrarily sized, positioned rectangles (as might be the case in a windowing system when dealing with window positions)?
是的,我有一个结构可以跟踪放置在屏幕上的一组窗口。我还有一个网格,它跟踪每个边缘之间的所有区域,无论它们是空的还是填充的,以及它们的左边缘或上边缘的像素位置。我认为有一些修改形式可以利用此属性。你知道吗?
最佳答案
我是 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]
上面的实现当然没什么特别的,但它与 Dr. Dobb 的文章中的解释非常接近,应该很容易翻译成任何需要的东西。
关于algorithm - 拼图 : Find largest rectangle (maximal rectangle problem),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7245/
我很绝望,现在已经两天(!!)天都没有解决方案来解决以下问题。 更新 Lion 后,我想使用最新版本的 rvm 安装额外的 rubies。 这是我之后调用 bundler 时发生的情况: /Users
我的问题: ajax 调用的无限循环会产生问题吗? 假设有这样的代码: ajaxcall(); function ajaxcall(){ jQuery.ajax({ typ
这是一个有趣的小项目,我已经开始尝试并最大限度地提高赢得办公室曲棍球池的机会。我试图找到最好的方法来选择 20 名能够在最高工资帽内给我最多分数的球员。 例如,假设原始数据由 玩家姓名 位置(前锋,后
我有一个总数为540000的数字列表。我想将此列表分为3个列表,每个列表总共180000。最有效的编程方法是这样做,假设数字列表是一个平面文件,每个数字为线? 最佳答案 听起来像Knapsack pr
抱歉,也许因为我不是英语,我不知道,但我找不到解决几个问题的任何资源;也许我用的词不正确.. 我想了解有关 iPhone 4 和 5 不同分辨率的更多信息。 首先:如果我开发针对 iPhone 4 分
在全局配置缓存后,如 docs ,如果我在 app.module 之外使用 CacheInterceptor,它会抛出错误。 app.module.ts const cacheConfig = {
我无法让 g:each 工作。我正在尝试遍历任何内容,但它永远不起作用 = 不生成任何 html。 索引.gsp Item ${i.name} 用户 Controller .g
在我的 XAML 文件中,我有一个这样声明的 ListBox:
想知道你是否可以帮助我: 我有一个名为initializeAll的方法: public final void initializeAll() { //other stuff........ rand
我尝试过使用 XML 和 JAVA 在我的 Android Activity 中创建一个 ImageView。这两次,我都能够获取我一天前创建的所有其他 PNG 资源以显示在 ImageView 中。
我需要你的帮助。这是什么意思? Warning: mysql_query() [function.mysql-query]: Access denied for user 'ODBC'
这是一段代码 function test() { this.value = "foo"; } $(document).ready(function () { test();
这是一些非常基础的东西。渲染期间引发异常:java.util.Locale.toLanguageTag()Ljava/lang/String; XML: 问题似乎出在 Edit
除其他来源外,我还使用 Stackoverflow 上的各种帖子,尝试实现我自己的 PHP 分类器,以将推文分类为正面、中性和负面类别。在编码之前,我需要弄清楚流程。我的思路和例子如下:
在过去的几周里,每当我在 Eclipse 上使用 SVN 插件时,我都会收到以下错误: Certificate Problem There is a problem with the site's s
我被拒绝运行以下功能(位于 /var/www/mysite/public_html/app/Controllers/Script.php) $structure = '/var/www/mysite/
我正在使用 ctags 为我的 Emacs 创建标签以使用 cygwin 从中读取符号。 Emacs 说 “访问标签表缓冲区:文件/home/superman/tags 不是有效的标签表” 这是我查找
我知道作为一种函数式语言,XSL 没有像传统的 for 循环(而是 for-each)那样的东西。 我正在尝试从可变数量的元素开始创建一个具有固定数量 (7) 的表。总之,我有
我正在使用RavenDB进行一些测试,以基于iphone应用程序存储数据。该应用程序将发送一个带有GPS key 的5个GPS坐标的字符串。我在RavenDB中看到每个文档约为664-668字节。这是
我无法理解我的应用程序的行为。我想创建一个简单的窗口 (1000x700px),分为两部分(分别为 250px 和 750px 宽度)。我尝试了以下代码: import java.awt.Color;
我是一名优秀的程序员,十分优秀!