Find largest rectangle in grid that rests on border and contains point
I have code that traverses a grid of free and "blocked" positions; and finds the largest possible rectangle.
This works just fine. However, I need to be able to find rectangle with more specific critera. Consider the following:
00X0000000
000000####
##########
####000000
0000000000
0000000000
In this diagram; 0 marks available positions, # marks occupied positions, and X marks a desired point.
The code I have now will find the bottom-right area of the grid, as that is truly the largest rectangle. However, the answer I want contains the X position (the top left rectangle).
I do not know how to go about adding this extra criteria. I tried to also keep track of coordinates; throwing out results that did not contain X; but this did not work all the time. Under certain conditions, I would get rectangles that were smaller than desired (probably because of the order I was traversing the grid)
All of the algorithms I have found seem to only capable of finding the largest rectangle, and the coordinates of the rectangle. I have not been able to find any that would be able to exclude results that do not contain a specific point reliably.
Could anyone point me in the right direction, and/or provide an implementation?
EDIT : Since comments cannot have newlines, I need to use this area to explain problems with shole's implementation. It fails for cases such as these:
#0#X
###0
#000
####
0#00
0000
0000
In the above example, the coordinates returned form a rect like this:
0#X
##0
000
answer should have been 1x3, not 3x3
Another example of failure:
0#X#
0000
00##
000#
0000
returns:
#X
00
In this case the answer returned should have been a 1x2 area, instead it thinks it is 2x2.
In some cases, it returns areas that are larger than the area of the entire grid, with coordinates outside of the range of valid coords.
This works SOMETIMES, but it is more often incorrect than it is correct. It does always return an area that contains the point though; just the wrong area/coords.
Interesting problem, here is my O(R*C) algorithm with R = # rows, C = #columns
The idea is simple, brute force every point as potential rectangles' bottom border, then try to climb up as high as possible to obtain maximum height, then get the largest left and right distance of this vertical line
This tests all potential rectangles, but we have to do it fast. We do it by dynamic programming, row by row, for each (i,j), calculating the maximum height, maximum left and right distance it can reach.
Then we can test if X is inside this potential rectangle, if yes, I add a infinite large offset to the area of this rectangle, it is large enough that any rectangle DOES NOT contains X will be smaller than it, while other rectangles, if contains X and larger than it, we still can choose that rectangle instead.
After the end of the algorithm, we get the maximum Area + Offset , we subtract the offset from it and get the area back.
It's more easy to understand if you run the code (C++) and see the log below, with following input:
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;
}上一篇: 最大的矩形设置封面
下一篇: 在网格中查找位于边界并包含点的最大矩形