在网格中查找位于边界并包含点的最大矩形
我有遍历自由和“封锁”位置的网格的代码; 并找到最大可能的矩形。
这工作得很好。 但是，我需要能够找到具有更多特定标准的矩形。 考虑以下：
00X0000000
000000####
##########
####000000
0000000000
0000000000
在该图中; 0表示可用位置，＃表示占用位置，X表示所需点。
我现在的代码将会找到网格的右下角区域，因为这是真正的最大的矩形。 但是，我想要的答案包含X位置（左上方的矩形）。
我不知道如何去添加这个额外的标准。 我也试着跟踪坐标; 抛出不包含X的结果; 但这并不是一直工作的。 在某些条件下，我会得到比想要的更小的矩形（可能是因为我正在穿越网格的顺序）
我发现的所有算法似乎只能找到最大的矩形和矩形的坐标。 我一直无法找到任何能够排除不包含可靠的特定点的结果。
任何人都可以向我指出正确的方向，并/或提供一个实施？
编辑 ：由于评论不能有换行符，我需要使用这个区域来解释shole实现的问题。 这种情况下失败：
#0#X
###0
#000
####
0#00
0000
0000
在上面的例子中，返回的坐标是这样形成的：
0#X
##0
000
答案应该是1x3，而不是3x3
失败的另一个例子：
0#X#
0000
00##
000#
0000
收益：
#X
00
在这种情况下，返回的答案应该是1x2的区域，而不是它认为是2x2。
在某些情况下，它返回的面积大于整个网格的面积，坐标超出有效坐标范围。
这工作有时候，但它往往是不正确的。 它总是返回一个包含点的区域; 只是错误的区域/坐标。
有趣的问题，这里是我的O（R * C）算法，R =＃行，C =＃列
这个想法很简单，强行将每个点作为潜在的矩形底部边界，然后尝试尽可能爬高以获得最大高度，然后获得该垂直线的最大左右距离
这测试所有潜在的矩形，但我们必须快速完成。 我们通过对每个（i，j）逐行进行动态编程来计算最大高度，最大左右距离。
然后我们可以测试X是否在这个潜在的矩形内，如果是的话，我为这个矩形的区域添加了一个无限大的偏移量 ，它足够大以至于任何矩形都不包含X将会比它更小，而其他矩形if包含X且大于它，我们仍然可以选择该矩形。
在算法结束后，我们得到最大面积+偏移量 ，我们从中减去偏移量并得到面积。
如果您运行代码（C ++）并通过以下输入查看下面的日志，则更容易理解：
6 10
00X0000000
000000####
##########
####000000
0000000000
0000000000
#include<bits/stdc++.h>
using namespace std;
char w[20][20];
int tl[20][20] = {0}, tr[20][20] = {0}, h[20][20] = {0}, l[20][20]={0}, r[20][20]={0};
int ans, R,C, xr,xc, ar1, ac1, ar2, ac2;
int largestRect()
{
int area = 0;
for(int i=0; i<20;i++) for(int j=0; j<20;j++) l[i][j] = r[i][j] = 1<<28;
for(int i=1; i<=R;i++){
for(int j=1; j<=C;j++)
if(w[i][j]!='#') tl[i][j] = tl[i][j-1]+1;
else tl[i][j] = 0;
for(int j=C; j>=1; j--)
if(w[i][j]!='#') tr[i][j] = tr[i][j+1]+1;
else tr[i][j] = 0;
for(int j=1; j<=C; j++)
if(w[i][j]!='#') h[i][j] = h[i-1][j]+1;
else h[i][j] = 0;
for(int j=1; j<=C; j++)
if(w[i][j] != '#') l[i][j] = min(tl[i][j], l[i-1][j]);
for(int j=1; j<=C; j++)
if(w[i][j] != '#') r[i][j] = min(tr[i][j], r[i-1][j]);
for(int j=1; j<=C;j++){
int offset = 0;
if((r[i][j]+l[i][j]-1)*h[i][j] > 0){
if(xr >= i-h[i][j]+1 && xr <= i && xc >= j-l[i][j]+1 && xc <= j+r[i][j]-1) offset = 1<<28;
printf("Top left = (%d,%d) Bottom right = (%d,%d)n", i-h[i][j]+1, j-l[i][j]+1,i, j+r[i][j]-1);
printf("Area = %dn", (r[i][j]+l[i][j]-1)*h[i][j]);
printf("Included X? %dn", xr >= i-h[i][j]+1 && xr <= i && xc >= j-l[i][j]+1 && xc <= j+r[i][j]-1 );
printf("Area with offset = %dnn", (r[i][j]+l[i][j]-1)*h[i][j] + offset);
if(area <= (r[i][j]+l[i][j]-1)*h[i][j] + offset){
area = max(area, (r[i][j]+l[i][j]-1)*h[i][j] + offset);
ar1 = i-h[i][j]+1; ac1 = j-l[i][j]+1; ar2 = i; ac2 = j+r[i][j]-1;
}
}
}
}
return area;
}
int main(){
scanf("%d %d", &R, &C);
for(int i=0; i<20;i++) for(int j=0; j<20;j++) w[i][j] = '#';
for(int i=1; i<=R; i++){
getchar();
for(int j=1; j<=C; j++){
w[i][j] = getchar();
if(w[i][j] == 'X'){ xr = i; xc = j;}
}
}
ans = largestRect() - (1<<28);
printf("Largest Rect Containing X is (%d,%d) to (%d,%d), with area = %dn", ar1, ac1, ar2, ac2, ans);
return 0;
}上一篇: Find largest rectangle in grid that rests on border and contains point
下一篇: how to find area of rectangle which is covering another rectangle