Интересная проблема, вот мой O (R * C) алгоритм с R = # строками, C = #columns
Идея проста, перебор каждая точка в нижних границах потенциальных прямоугольников, то попробуйте подняться как можно выше, чтобы получить максимальную высоту, а затем получить самое большое левое и правое расстояние этой вертикальной линии
Это проверяет все возможные прямоугольники, но мы должны сделать это быстро. Мы делаем это путем динамического программирования по строкам, для каждого (i, j), вычисляя максимальную высоту, максимально возможное расстояние слева и справа.
Тогда мы можем проверить, если X находится внутри этого потенциального прямоугольника, если да, то я добавить бесконечное большое смещение площади этого прямоугольника, достаточно велико, что любой прямоугольник не содержит X, будет меньше, чем это , в то время как другие прямоугольники, если они содержат 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;
\t for(int i=1; i<=R;i++){
\t for(int j=1; j<=C;j++)
\t \t if(w[i][j]!='#') tl[i][j] = tl[i][j-1]+1;
\t \t \t else tl[i][j] = 0;
\t \t for(int j=C; j>=1; j--)
\t \t \t if(w[i][j]!='#') tr[i][j] = tr[i][j+1]+1;
\t \t \t else tr[i][j] = 0;
\t \t
\t \t for(int j=1; j<=C; j++)
\t \t \t if(w[i][j]!='#') h[i][j] = h[i-1][j]+1;
\t \t \t else h[i][j] = 0;
\t \t
\t \t for(int j=1; j<=C; j++)
\t \t \t if(w[i][j] != '#') l[i][j] = min(tl[i][j], l[i-1][j]);
\t \t
\t \t for(int j=1; j<=C; j++)
\t \t \t if(w[i][j] != '#') r[i][j] = min(tr[i][j], r[i-1][j]);
\t
\t \t
\t \t for(int j=1; j<=C;j++){
\t \t \t int offset = 0;
\t \t \t if((r[i][j]+l[i][j]-1)*h[i][j] > 0){
\t \t \t if(xr >= i-h[i][j]+1 && xr <= i && xc >= j-l[i][j]+1 && xc <= j+r[i][j]-1) offset = 1<<28;
\t \t \t \t 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);
\t \t \t \t printf("Area = %d\n", (r[i][j]+l[i][j]-1)*h[i][j]);
\t \t \t \t printf("Included X? %d\n", xr >= i-h[i][j]+1 && xr <= i && xc >= j-l[i][j]+1 && xc <= j+r[i][j]-1);
\t \t \t \t printf("Area with offset = %d\n\n", (r[i][j]+l[i][j]-1)*h[i][j] + offset);
\t \t \t \t \t
\t \t \t \t if(area <= (r[i][j]+l[i][j]-1)*h[i][j] + offset){
\t \t \t \t \t area = max(area, (r[i][j]+l[i][j]-1)*h[i][j] + offset);
\t \t \t \t \t \t ar1 = i-h[i][j]+1; ac1 = j-l[i][j]+1; ar2 = i; ac2 = j+r[i][j]-1;
\t \t \t \t }
\t \t \t }
\t \t }
\t }
return area;
}
int main(){
\t scanf("%d %d", &R, &C);
\t
\t for(int i=0; i<20;i++) for(int j=0; j<20;j++) w[i][j] = '#';
\t
\t for(int i=1; i<=R; i++){
\t \t getchar();
\t \t for(int j=1; j<=C; j++){
\t \t \t w[i][j] = getchar(); \t
\t \t \t if(w[i][j] == 'X'){ xr = i; xc = j;}
\t \t }
\t }
\t
\t ans = largestRect() - (1<<28);
\t printf("Largest Rect Containing X is (%d,%d) to (%d,%d), with area = %d\n", ar1, ac1, ar2, ac2, ans);
\t return 0; \t
}
EDITED ЧАСТЬ: Алгоритм/код Разъясняется в деталях
Прежде всего, вот контур нашего O (R * C) algo rithm:
- перебор каждый пустой точка в сетке, использовать его в качестве точки нижней границы нашего потенциального крупнейшего пустого прямоугольника. Это O (R * C)
- Для каждой точки, я хочу идти вверх, насколько это возможно, давайте определим h [i] [j] - это массив, означающий максимальную высоту, с которой вы можете добраться, начиная с (i, к)
- Теперь я хочу знать, как далеко я могу пойти налево и направо, в пределах этого вертикального диапазона сегмента
- я получаю высоту, я получаю самую длинную длину справа и слева я могу достичь в пределах этой высоты, поэтому я могу, конечно, рассчитать площадь этого прямоугольника
- Получите максимум от площади каждого прямоугольника, повторяя шаг 1-4
Затем мы увидим, как сделать шаг 2-3 в алгоритме, мы будем использовать Динамическое программирование.
Давайте определим несколько массива:
h[i][j] := the highest height you can reach starting at (i,j)
tr[i][j] := the longest distance to right you can reach starting at (i,j)
tl[i][j] := the longest distance to left you can reach starting at (i,j)
Один должен быть в состоянии видеть, что эти три массива может быть предвычислением с использованием O (R * C)
h[i][j] = h[i-1][j]+1 if(i,j) is empty, else h[i][j] = 0
similarly
tr[i][j] = tr[i][j+1]+1 if(i,j) is empty, else tr[i][j] = 0
tl[i][j] = tl[i][j-1]+1 if(i,j) is empty, else tl[i][j] = 0
Теперь определит еще два массива
l[i][j] := the longest distance to right you can reach starting from
line (i,j) and (i-h[i][j]+1,j) (That's simply just put h[i][j] into consideration)
Как и в случае с r [i] [j], убедитесь, что вы выдержать разницу между tl [i] [j] и l [i] [j] (tr [i] [j] и r [i] [j])
Теперь l [i] [j] и r [i] [j] также может быть предварительно вычислено с использованием O (R * C)!
Небольшое отличие состоит в том, что они нуждаются в час [I] [J] и тр [I] [J] (или TL [I] [J]), чтобы вычислить его,
так ч [I] [ j], tl [i] [j], tr [i] [j] должно быть вычислено до l [i] [j] и r [i] [j].
l[i][j] = min(l[i-1][j], tl[i][j]) if(i,j) is empty, else l[i][j] = tl[i][j]
r[i][j] = min(r[i-1][j], tr[i][j]) if(i,j) is empty, else r[i][j] = tr[i][j]
Вы можете думать, что он говорит следующие утверждения:
л [я] [J] является минимум ТЛ [X] [J], X в [Шс [я ] [J] + 1, я]
Так л [я] [J] максимальное расстояние влево в пределах (I, J) на максимальную высоту
Подобно г [I] [ j]
Так что мой код использует два для петель делают именно динамическое программирование описано выше, это кажется сложным, потому что я не предвычисление их всех перед их использованием
Я вычислить эти массивы и использовать их для вычисления прямоугольника площадь на лету. Говоря, вы всегда можете предварительно скомпоновать все эти массивы, а затем вычислить максимальные площади впоследствии, сложность по времени еще равна O (R * C)
Не являются ли нижние две линии наибольшим прямоугольником? «Площадь» - 20 (количество нулей). В правом нижнем углу находится область 18. – user1952500
Вы правы. Я это заметил. Основная идея состоит в том, что я не хочу возвращать ни один из нижних прямоугольников, только тот, у которого есть X-точка. – dmarra
Вы можете начать с X и идти вверх, вниз, влево и вправо (как пульсация) и развернуть, пока не получите «#». Координаты вблизи хеша будут одной из конечных точек такого максимального прямоугольника. – user1952500