#include <windows.h>
#include <stdio.h>
#include <conio.h>
int field[10][10] = {
0, 0, 1, 0, 0, 0, 1, 1, 0, 0,
0, 1, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 1, 0, 0, 0, 1, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0, 1, 0,
0, 0, 0, 0, 0, 0, 1, 0, 1, 0,
0, 0, 0, 0, 0, 1, 1, 1, 1, 1,
0, 1, 0, 0, 0, 0, 1, 0, 0, 1,
0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
1, 0, 0, 1, 0, 1, 1, 0, 1, 0,
0, 1, 0, 0, 1, 0, 1, 0, 1, 0
};
void findMaxRect(int *iArray, int nSize);
int main(int argc, char* argv[])
{
findMaxRect(field[0], 10);
return 0;
}
int compare( const void *arg1, const void *arg2 )
{
return *(int *)arg1 - *(int *)arg2;
}
void findMaxRect(int *iArray, int nSize)
{
DWORD dwSize = sizeof(int)*(3*nSize*nSize + 4*nSize + 4);
void *field = VirtualAlloc(NULL,dwSize,MEM_RESERVE|MEM_COMMIT| MEM_TOP_DOWN,PAGE_READWRITE);
int *ipAr = (int *)field + nSize + 3;
int i, j;
for(i=0; i<nSize; i++)
{
for(j=0; j<nSize; j++)
{
*ipAr = *iArray;
ipAr++;
iArray++;
}
ipAr+=2;
}
ipAr = (int *)field + nSize + 3;
int maxItemCnt = 0;
int *iCurRes = (int *)field + nSize*nSize + 4*nSize + 4;
int *iMaxRes = iCurRes + nSize*nSize;
int nSize2 = nSize + 2;
for(i=1; i<nSize-1; i++)
{
for(j=1; j<nSize-1; j++)
{
if(*ipAr==1)
{
*ipAr = 0;
*iCurRes = (int)ipAr;
int *iCurResLimit = iCurRes;
int iCnt = 1;
int *iItem = iCurRes;
while(iItem<=iCurResLimit)
{
int *ip = (int *)*iItem - nSize2;
if(*ip==1)
{
*ip = 0;
iCurResLimit++;
*iCurResLimit = (int)ip;
iCnt++;
}
ip = (int *)*iItem + 1;
if(*ip==1)
{
*ip = 0;
iCurResLimit++;
*iCurResLimit = (int)ip;
iCnt++;
}
ip = (int *)*iItem + nSize2;
if(*ip==1)
{
*ip = 0;
iCurResLimit++;
*iCurResLimit = (int)ip;
iCnt++;
}
ip = (int *)*iItem - 1;
if(*ip==1)
{
*ip = 0;
iCurResLimit++;
*iCurResLimit = (int)ip;
iCnt++;
}
iItem++;
}
if(maxItemCnt<iCnt)
{
maxItemCnt = iCnt;
CopyMemory(iMaxRes, iCurRes, sizeof(int)*iCnt);
}
}
ipAr++;
}
ipAr+=2;
}
printf("Число ячеек: %d\n\n", maxItemCnt);
qsort((void *)iMaxRes, maxItemCnt, sizeof(int), compare);
for(int k=0; k<maxItemCnt; k++)
{
j = (*iMaxRes - (int)field)>>2;
i = j/nSize2;
j-= i*nSize2 - 1;
i--;
printf("Ячейка (%d, %d)\n", i, j);
iMaxRes++;
}
printf("\nНажмите любую клавишу...\n");
VirtualFree(field, 0, MEM_RELEASE);
getch();
}
Разминка для ума
Интересную задачку подкинули:
Есть клетчатое поле NxN.
Клетки этого поля могут быть белыми и черными в некотором хаотичном порядке.
Необходимо найти площадь максимального белого прямоугольника.
Цитата:
Есть клетчатое поле NxN.
Клетки этого поля могут быть белыми и черными в некотором хаотичном порядке.
Необходимо найти площадь максимального белого прямоугольника.
Ну что, кто может предложить алгоритм, а заодно и определить его асимптотическую сложность?
Кстати, может кто предложит к какой сложности надо стремится? :)
P.S. Чужие варианты (если кто знает ответ) не предлагать, только свои мысли.
Хм..
Запутанный алгоритм. Честно говоря, я так и не понял, как он работает, и работает ли вообще, т.к. ответ мне не ясен:
Cell number: 10
cell (3, 10)
cell (4, 8)
cell (4, 10)
cell (5, 7)
cell (5, 8)
cell (5, 9)
cell (5, 10)
cell (5, 11)
cell (6, 8)
cell (6, 11)
Запутанный алгоритм. Честно говоря, я так и не понял, как он работает, и работает ли вообще, т.к. ответ мне не ясен:
Цитата:
Cell number: 10
cell (3, 10)
cell (4, 8)
cell (4, 10)
cell (5, 7)
cell (5, 8)
cell (5, 9)
cell (5, 10)
cell (5, 11)
cell (6, 8)
cell (6, 11)
Для понимания задачи уточню, что для клетчатого поля твоего примера максимальный белый прямоугольник показан на рисунке
Есть ещё мысли?
Желательно приводить все же алгоритм, а не код.
Т.к. иногда в коде сложно разобраться. :)
При описании алгоритма не сосредотачивайтесь на "областях памяти", указателях и т.п. Это все уже реализация, а нужен просто обобщенный алгоритм с указанием его сложности ( зависимость количества операций от размерности поля O = f(N) )
Для начала определимся с самым быстрым алгорнитмом, а потом подумаем, как его реализовать.
Желательно приводить все же алгоритм, а не код.
Т.к. иногда в коде сложно разобраться. :)
При описании алгоритма не сосредотачивайтесь на "областях памяти", указателях и т.п. Это все уже реализация, а нужен просто обобщенный алгоритм с указанием его сложности ( зависимость количества операций от размерности поля O = f(N) )
Для начала определимся с самым быстрым алгорнитмом, а потом подумаем, как его реализовать.
Цитата:
Originally posted by Green
Для начала определимся с самым быстрым алгорнитмом, а потом подумаем, как его реализовать.
Для начала определимся с самым быстрым алгорнитмом, а потом подумаем, как его реализовать.
Предлагаю алгоритм "Сапера" (не проверял):
- первый проход: для каждого белого квадратика смотрим на соседние по горизонтали и вертикали и вписываем в ячейку соответствующее число
- второй проход: находим самое большое число и считаем площадь (сумму), потом пытаемся найти число, равное предыдущему и считаем площадь для нового квадратика, и т. д.
Выигрывает область с наибольшей площадью.
Цитата:
Originally posted by Green
Хм.. Запутанный алгоритм.
Хм.. Запутанный алгоритм.
1. Проходим по элементам матрицы - слева направо, сверху вниз.
2. Для белой ячейки определяем площадь белой области, в которую она входит.
3. Чтоб каждая ячейка проверялась только один раз, меняем цвет проверенной белой ячейки на черный.
4. Из всех площадей выбираем максимальный.
Что Тебе не понятно? :)
Цитата:
Честно говоря, я так и не понял, как он работает, и работает ли вообще, т.к. ответ мне не ясен:
Код работает, и делает то, что от него требуется: находить макс. белую связанную область. Прилагаю скриншот. Другой вопрос, что я не заметил, что область должна быть прямоугольной.
Мимоходом, Freeman уже говорит о квадратиках. :)
На счет задачи напишу в след.отв., так как можно прикрепить только одну картинку.
1. Проходим по элементам матрицы - слева направо, сверху вниз.
2. Для белой ячейки определяем площадь белой прямоугольной области, в которую она входит.
3. Из всех площадей выбираем максимальный.
Чтоб код приведенный мною, делал это, нужно убрать два блока, которые проверяют соседи сверху и слева и добавить 3х переменных. Две связаны с шириной рассматриваемой области, одна с высотой. И конечно нужен код, обрабатывающий значния этих переменнных.
Но алгоритм будет неоптимальным, так как неможно менять цвет проверенных ячеек. Поэтому одна и та же ячейка может быть проверена несколько раз, какой цвет она имеет.
Один из способов усовершенствовать этот алгоритм, это запустить прогу, что выше, и сперва выделить ВСЕ белые области(скриншот(1)). Паралельно заполнять multimap, ключ: количесво ячеек области, элемент: указатель на первую ячейку.
Прога сверху вернет адреса белых ячеек, без черных. Т.е. в данном случае имеем дело с 10 ячейками, а не с 20, и цвет каждой ячейки проверяется только один раз. И задача сводится к тому, что в этой структуре (скриншот(2)) найти макс. прямоугольную область.
На счет multimap. Нужно начать определение макс. прямоугольной области с последней записи (т.е. проходить по сруктуре сзади наперед). И вести поиск до тех пор, пока площадь текущей макс. области не станет больше ключа, текущего элемента multimap. Это может отсечь довольно много вариантов.
2. Для белой ячейки определяем площадь белой прямоугольной области, в которую она входит.
3. Из всех площадей выбираем максимальный.
Чтоб код приведенный мною, делал это, нужно убрать два блока, которые проверяют соседи сверху и слева и добавить 3х переменных. Две связаны с шириной рассматриваемой области, одна с высотой. И конечно нужен код, обрабатывающий значния этих переменнных.
Но алгоритм будет неоптимальным, так как неможно менять цвет проверенных ячеек. Поэтому одна и та же ячейка может быть проверена несколько раз, какой цвет она имеет.
Один из способов усовершенствовать этот алгоритм, это запустить прогу, что выше, и сперва выделить ВСЕ белые области(скриншот(1)). Паралельно заполнять multimap, ключ: количесво ячеек области, элемент: указатель на первую ячейку.
Прога сверху вернет адреса белых ячеек, без черных. Т.е. в данном случае имеем дело с 10 ячейками, а не с 20, и цвет каждой ячейки проверяется только один раз. И задача сводится к тому, что в этой структуре (скриншот(2)) найти макс. прямоугольную область.
На счет multimap. Нужно начать определение макс. прямоугольной области с последней записи (т.е. проходить по сруктуре сзади наперед). И вести поиск до тех пор, пока площадь текущей макс. области не станет больше ключа, текущего элемента multimap. Это может отсечь довольно много вариантов.
Цитата:
Originally posted by Freeman
Предлагаю алгоритм "Сапера" (не проверял):
- первый проход: для каждого белого квадратика смотрим на соседние по горизонтали и вертикали и вписываем в ячейку соответствующее число
- второй проход: находим самое большое число и считаем площадь (сумму), потом пытаемся найти число, равное предыдущему и считаем площадь для нового квадратика, и т. д.
Выигрывает область с наибольшей площадью.
Предлагаю алгоритм "Сапера" (не проверял):
- первый проход: для каждого белого квадратика смотрим на соседние по горизонтали и вертикали и вписываем в ячейку соответствующее число
- второй проход: находим самое большое число и считаем площадь (сумму), потом пытаемся найти число, равное предыдущему и считаем площадь для нового квадратика, и т. д.
Выигрывает область с наибольшей площадью.
Алгоритм, конечно, далеко не точный, но уже просматривается сложность где-то N в шестой степени.
Можно быстрее.
К какой сложности будем стремится?
Цитата:
Originally posted by Mоngооsе
1. Проходим по элементам матрицы - слева направо, сверху вниз.
1. Проходим по элементам матрицы - слева направо, сверху вниз.
N^2
(знаком ^ буду обозначать степень)
Цитата:
Originally posted by Mоngооsе
2. Для белой ячейки определяем площадь белой прямоугольной области, в которую она входит.
2. Для белой ячейки определяем площадь белой прямоугольной области, в которую она входит.
N^2
Цитата:
Originally posted by Mоngооsе
3. Из всех площадей выбираем максимальный.
3. Из всех площадей выбираем максимальный.
N^2
Итого: N^6
P.S. Давай пока не будем прявязываться к адресам и мультимепам, это уже реализация.
Цитата:
Originally posted by Green
Есть клетчатое поле NxN.
Клетки этого поля могут быть белыми и черными в некотором хаотичном порядке.
Необходимо найти площадь максимального белого прямоугольника
Есть клетчатое поле NxN.
Клетки этого поля могут быть белыми и черными в некотором хаотичном порядке.
Необходимо найти площадь максимального белого прямоугольника
Пройти входную матрицу по строчкам.
Запоминать площадь прямоугольников которые пресекаютсь строчкой начиная с и-того столбца и длинной в джей столбцов
Для слудующей строчки додавать до площади длинну если прямоугольник в ней продолжается или обнулят площадь если не продолжается.
Когда обнуляем надо запоминать максимум. В конце также придется оставшиися площади на максимум проверить.
Входную матрицу позначим M[N][N]
Надо треугольною матрицу S[N][N]
Ее размер соответственно N*(N+1)/2 елементов
Она инициализирована нулями.
Еще финальный результат позначим MAX = 0
Входную матрицу сканирую по строчкам.
Код:
Для каждой строчки делать
для i от 0 до N-1 делать // ето цыкл по началу отрезка в срочке
{
былличерный = нет // когда станет "да" значит в отрезке уже
// встретился черный кв.
для j от 0 до N-1-i делать // ето цыкл по длинне отрезка
{
если (M[номер строчки][i+j] == черный) тогда былличерный = да
если (былличерный == да) тогда
{ // обнуляем и ищим максимум
если (MAX < S[j]) тогда MAX = S[j]
S[j] = 0
}
иначе
{ // увеличиваем площадь
S[j] = S[j] + j+1 // j-длинна, +1 потому что j c нуля
}
}
}
// Проверка оставшихся площадей на максимум
для i от 0 до N-1 делать
для j от 0 до N-1-i делать
если (MAX < S[j]) тогда MAX = S[j]
Результат в MAX
для i от 0 до N-1 делать // ето цыкл по началу отрезка в срочке
{
былличерный = нет // когда станет "да" значит в отрезке уже
// встретился черный кв.
для j от 0 до N-1-i делать // ето цыкл по длинне отрезка
{
если (M[номер строчки][i+j] == черный) тогда былличерный = да
если (былличерный == да) тогда
{ // обнуляем и ищим максимум
если (MAX < S[j]) тогда MAX = S[j]
S[j] = 0
}
иначе
{ // увеличиваем площадь
S[j] = S[j] + j+1 // j-длинна, +1 потому что j c нуля
}
}
}
// Проверка оставшихся площадей на максимум
для i от 0 до N-1 делать
для j от 0 до N-1-i делать
если (MAX < S[j]) тогда MAX = S[j]
Результат в MAX
Я не проверял работает ли оно но должно бы :)
Сложность N*N*(N+1)/2 + N*(N+1)/2 = N*(N+1)^2 / 2 = чуть бодльше N^3
Второй доданок ето проверка оставшихся площадей
PS Мой друг Юра 7th(вы случайно с ним не знакомы ???) недавно расказал мне более изяшный алгоритм который работает быстрее.
Он его прочел в какойто еще советской книге по олимпиадным задачам по программированию.
Етому алгоритму не нужна треугольная матрица сум, а только исходная.
Но ето уже чужая мысль :)
Цитата:
Originally posted by Green
N^2
(знаком ^ буду обозначать степень)
N^2
N^2
Итого: N^6
N^2
(знаком ^ буду обозначать степень)
N^2
N^2
Итого: N^6
N^6 это в худшем случае, но от алгоритма полного перебора другого ждать и не можно было бы.
Но я писал ниже, как можно этот алгоритм усовершенствовать.
Сперва с программой подобной что я выше написал, выделить все связанные белые области. Это N^2.
Из этих областей выделить прямоугольные и определить макс. Это в любом случае меньше, чем N^2. Т.е. получается трудоемкость N^2
На счет не привязки к реализации. От реализации многое зависит.
Цитата:
Originally posted by Green
Интересную задачку подкинули:
Ну что, кто может предложить алгоритм, а заодно и определить его асимптотическую сложность?
Кстати, может кто предложит к какой сложности надо стремится? :)
P.S. Чужие варианты (если кто знает ответ) не предлагать, только свои мысли.
Интересную задачку подкинули:
Ну что, кто может предложить алгоритм, а заодно и определить его асимптотическую сложность?
Кстати, может кто предложит к какой сложности надо стремится? :)
P.S. Чужие варианты (если кто знает ответ) не предлагать, только свои мысли.
Код:
var
a,a1:array[1..10,1..10] of integer;
v:array[1..10] of integer;
i,j,b,c,d,max:integer;
Begin
randomize;
For i:=1 to 10 do begin
for j:=1 to 10 do
a[i,j]:=random(2)
end;
For i:=1 to 10 do begin
for j:=1 to 10 do
write(a[i,j]:3);
writeln;
End;
writeln;
a1:=a;
For i:=1 to 10 do begin
c:=0;
for j:=1 to 10 do
if a[i,j]=1 then begin a[i,j]:=0; b:=1; c:=0 end
else if (a[i,j]=0) and (b=0) then begin inc(c); a[i,j]:=c; b:=0; end
else begin a[i,j]:=1; b:=0; c:=1 end;
end;
For i:=1 to 10 do begin
for j:=1 to 10 do
write(a[i,j]:3);
writeln;
End;
readln;
end.
a,a1:array[1..10,1..10] of integer;
v:array[1..10] of integer;
i,j,b,c,d,max:integer;
Begin
randomize;
For i:=1 to 10 do begin
for j:=1 to 10 do
a[i,j]:=random(2)
end;
For i:=1 to 10 do begin
for j:=1 to 10 do
write(a[i,j]:3);
writeln;
End;
writeln;
a1:=a;
For i:=1 to 10 do begin
c:=0;
for j:=1 to 10 do
if a[i,j]=1 then begin a[i,j]:=0; b:=1; c:=0 end
else if (a[i,j]=0) and (b=0) then begin inc(c); a[i,j]:=c; b:=0; end
else begin a[i,j]:=1; b:=0; c:=1 end;
end;
For i:=1 to 10 do begin
for j:=1 to 10 do
write(a[i,j]:3);
writeln;
End;
readln;
end.
b - признак что до этого был белый цвет!
кСТА для столбцов - повторить!
Цитата:
Originally posted by Greenering
b - признак что до этого был белый цвет!
кСТА для столбцов - повторить!
b - признак что до этого был белый цвет!
кСТА для столбцов - повторить!
Очень даже красиво, но так Ты найдеш самий длинний прямоугольник высотой в 1 (или толощиной в 1 если будеш ити по столбцам). А если прямоугольник 2х3 ???.
Но вообще ето есть первая половина хорошого алгоритма для решения етой задачи. :) Только по столбцам не повторить надо, а кое что другое ...
Цитата:
Originally posted by Greenering
b - признак что до этого был белый цвет!
кСТА для столбцов - повторить!
Код:
var
a,a1:array[1..10,1..10] of integer;
...
skipped
...
a,a1:array[1..10,1..10] of integer;
...
skipped
...
кСТА для столбцов - повторить!
Круто. Особенно, если учесть, что Green просто фанат языка Pascal. :)
Но требует N^2 операций в обоих направлениях.
При выделении непрерывных белых областей можно получить адреса тех ячеек, которые не имеют соседей справа. На скриншоте они пронумерованы. И просто взять эти ячейки. Записать в них одиницу, и двигаться налево, проставляя число пройденных ячеек, пока есть сосед слева.
Вертикально аналогично, для ячеек не имеющих соседей снизу.
С красным на скриншоте помечены те ячейки, для которых нужно посчитать область макс. прямоугольника, левым-верхним углом которых они являются.
Цитата:
Originally posted by Rebbit
Очень даже красиво, но так Ты найдеш самий длинний прямоугольник высотой в 1 (или толощиной в 1 если будеш ити по столбцам). А если прямоугольник 2х3 ???.
Но вообще ето есть первая половина хорошого алгоритма для решения етой задачи. :) Только по столбцам не повторить надо, а кое что другое ...
Очень даже красиво, но так Ты найдеш самий длинний прямоугольник высотой в 1 (или толощиной в 1 если будеш ити по столбцам). А если прямоугольник 2х3 ???.
Но вообще ето есть первая половина хорошого алгоритма для решения етой задачи. :) Только по столбцам не повторить надо, а кое что другое ...
Точно! Но в свою защиту скажу что ориентировалась на пример прикрепленный Green-ом. Так чтоже делать, если не по-столбцам?
Цитата:
Originally posted by Mоngооsе
Круто. Особенно, если учесть, что Green просто фанат языка Pascal. :)
Но требует N^2 операций в обоих направлениях.
Круто. Особенно, если учесть, что Green просто фанат языка Pascal. :)
Но требует N^2 операций в обоих направлениях.
итого N^4!
Цитата:
Originally posted by Greenering
итого N^4!
итого N^4!
Не а. 2 * N^2.
Цитата:
Originally posted by Greenering
... Так чтоже делать, если не по-столбцам?
... Так чтоже делать, если не по-столбцам?
Для начала исправить баги. :)
Цитата:
Originally posted by Mоngооsе
Для начала исправить баги. :)
Для начала исправить баги. :)
Там нет багов!!!!!!
Цитата:
Originally posted by Greenering
Так чтоже делать, если не по-столбцам?
Так чтоже делать, если не по-столбцам?
Таки по столбцам. Но делать надо не тоже самое, а другое. А что не скажу потомучто
PS Чужие варианты (если кто знает ответ) не предлагать, только свои мысли :)
Свою мысль я уже сказал в первом посте на ету тему, а етот алгоритм который Ты начала мне розказали. Скажу только что идти надо по столбцам справа налево. И помни, что если у прямоугольника стороны a & b, то площадь = a*b
Интересно програмировать не кнопки, а алгоритмы :) (ИМХО)
PS. Я ошибся. Справа на лево или слева направо - ето не принципиально.
Цитата:
Originally posted by Green
Интересную задачку подкинули:
Ну что, кто может предложить алгоритм, а заодно и определить его асимптотическую сложность?
Кстати, может кто предложит к какой сложности надо стремится? :)
P.S. Чужие варианты (если кто знает ответ) не предлагать, только свои мысли.
Интересную задачку подкинули:
Ну что, кто может предложить алгоритм, а заодно и определить его асимптотическую сложность?
Кстати, может кто предложит к какой сложности надо стремится? :)
P.S. Чужие варианты (если кто знает ответ) не предлагать, только свои мысли.
Алгоритм
Берем текущую белую клетку и считаем все белые клетки, на пересечении которых она находится, т.е. сколько белых клеток вверх, вниз, влево и вправо. Запоминаем число по вертикали, по горизонтали и отдельно количество клеток вверх, вниз, влево и вправо – далее начальные данные.
Вариант №1 и №2 – горизонтальные и вертикальные полосы.
Проверка по вертикали.
Для каждой клетки (сначала вверх, потом вниз) проверяем количество белых клеток справа и слева от нее, не вылезая за пределы начальных данных, и попутно редактируем их. Это вариант №3. Вариант №4 – то же самое, но начинаем снизу, а потом вверх и начальные данные те, которые получили вначале.
Проверка по горизонтали.
То же самое, что и в предыдущем пункте, но по горизонтали.
Все клетки, вошедшие в найденные прямоугольники, в расчет уже не брать в качестве точки отправления. Потому как результат будет тем же самым.
Пример для клетки, помеченной крестиком.
Начальные данные:
Vert = 5, Horiz = 4 – Вариант №1 и №2
Rect = 1, 2, 3, 1 (Rect = влево, вправо, вверх, вниз)
Проверка по вертикали.
(вверх, вниз)
Rect = 0, 1, 3, 1 – 1 клетка вверх (влево нет клеток, значит убираем клетку слева; вправо всего одна)
Rect = 0, 1, 1, 1 – 2 клетка вверх (вправо нет клеток – прямоугольник закончился на предыдущей. удаляем)
Rect = 0, 1, 1, 1 – 1 клетка вниз (вправо есть клетка, оставляем)
Вариант №3: Прямоугольник 3x2 (синий)
(вниз, вверх)
Rect = 1, 2, 3, 1 – 1 клетка вниз (влево 1 клетка, вправо 2 – оставляем все как есть)
Rect = 1, 2, 0, 1 – 1 клетка вверх (влево нет клеток – прямоугольник закончился на предыдущей. удаляем)
Вариант №4: Прямоугольник 2x4 (зеленый)
Проверка по горизонтали.
(вправо, влево)
Rect = 1, 2, 1, 1 – 1 клетка вправо (вверх одна клетка, вниз тоже)
Rect = 1, 1, 1, 1 – 2 клетка вправо (нет клеток вверх, удаляем)
Rect = 0, 1, 1, 1 – 1 клетка влево (нет клеток вверх, удаляем)
Вариант №5: Прямоугольник 3x2
(влево, вправо)
Rect = 1, 2, 0, 1 – 1 клетка влево (вниз одна клетка, вверх нет)
Rect = 1, 2, 0, 1 – 1 клетка вправо (вниз одна клетка, вверх не нужна)
Rect = 1, 2, 0, 1 – 2 клетка вправо (вниз одна клетка, вверх нет)
Вариант №5: Прямоугольник 2x4
N^:-?
Надеюсь не слишком сильно запутал алгоритм. :)
С картинкой стормозил. Извеняйте!
М-да... многое я пропустил. Постараюсь наверстать.
Mоngооsе, мне кажется вся сложность и уязвимость твоего алгоритма в том, что ты сначала ищешь области, потом среди этих областей прямоугольники, а потом среди этих прямоугольников наибольший.
Как будет работать твой алгоритм в случае, если все поле белое и лишь одна клеточка черная? Не придется ли дважды выполнять одну и ту же работу.
Кстати, по поводу алгоритмов и реализации, профессиональный программист должен четко разделять эти вещи и уметь независимо работать над ними.
Rebbit, я взял поле 4х4:
Для первой же строчки я получил следущее S:
MAX = 2
Что-то мне подсказывает, что это уже не то, что ты хотел.
Кроме того я не вижу связи между строчками.
Само же описание алгоритма мне понравилось, как и подсчет сложности, хотя вместо "для i от 0 до N-1 делать" я бы написал "для каждой ячейки строки" и т.п.
P.S. Чуть позднее рассмотрю остальные алгоритмы.
Mоngооsе, мне кажется вся сложность и уязвимость твоего алгоритма в том, что ты сначала ищешь области, потом среди этих областей прямоугольники, а потом среди этих прямоугольников наибольший.
Как будет работать твой алгоритм в случае, если все поле белое и лишь одна клеточка черная? Не придется ли дважды выполнять одну и ту же работу.
Кстати, по поводу алгоритмов и реализации, профессиональный программист должен четко разделять эти вещи и уметь независимо работать над ними.
Rebbit, я взял поле 4х4:
Код:
1 1 0 1
1 1 1 1
0 0 1 1
1 0 1 1
1 1 1 1
0 0 1 1
1 0 1 1
Для первой же строчки я получил следущее S:
Код:
1 2 0 4
2 0 4
0 4
4
2 0 4
0 4
4
MAX = 2
Что-то мне подсказывает, что это уже не то, что ты хотел.
Кроме того я не вижу связи между строчками.
Само же описание алгоритма мне понравилось, как и подсчет сложности, хотя вместо "для i от 0 до N-1 делать" я бы написал "для каждой ячейки строки" и т.п.
P.S. Чуть позднее рассмотрю остальные алгоритмы.
Цитата:
Originally posted by bqserg
Берем текущую белую клетку и считаем все белые клетки, на пересечении которых она находится, т.е. сколько белых клеток вверх, вниз, влево и вправо. Запоминаем число по вертикали, по горизонтали и отдельно количество клеток вверх, вниз, влево и вправо – далее начальные данные.
Берем текущую белую клетку и считаем все белые клетки, на пересечении которых она находится, т.е. сколько белых клеток вверх, вниз, влево и вправо. Запоминаем число по вертикали, по горизонтали и отдельно количество клеток вверх, вниз, влево и вправо – далее начальные данные.
Для одной клетки - N^2, для всех - N^4
Цитата:
Originally posted by bqserg
Вариант №1 и №2 – горизонтальные и вертикальные полосы.
Проверка по вертикали.
Для каждой клетки (сначала вверх, потом вниз) проверяем количество белых клеток справа и слева от нее, не вылезая за пределы начальных данных, и попутно редактируем их. Это вариант №3. Вариант №4 – то же самое, но начинаем снизу, а потом вверх и начальные данные те, которые получили вначале.
Вариант №1 и №2 – горизонтальные и вертикальные полосы.
Проверка по вертикали.
Для каждой клетки (сначала вверх, потом вниз) проверяем количество белых клеток справа и слева от нее, не вылезая за пределы начальных данных, и попутно редактируем их. Это вариант №3. Вариант №4 – то же самое, но начинаем снизу, а потом вверх и начальные данные те, которые получили вначале.
Пропорционально N^3
Цитата:
Originally posted by bqserg
Проверка по горизонтали.
То же самое, что и в предыдущем пункте, но по горизонтали.
Проверка по горизонтали.
То же самое, что и в предыдущем пункте, но по горизонтали.
Пропорционально N^3
Далее сравнение всех прямоугольников - N^4.
Цитата:
Originally posted by bqserg
Все клетки, вошедшие в найденные прямоугольники, в расчет уже не брать в качестве точки отправления. Потому как результат будет тем же самым.
Все клетки, вошедшие в найденные прямоугольники, в расчет уже не брать в качестве точки отправления. Потому как результат будет тем же самым.
Оптимизация. В худшем случае (шахматная доска) не срабатывает.
Итого: пропорционально N^4
Цитата:
Originally posted by Greenering
Так чтоже делать, если не по-столбцам?
Так чтоже делать, если не по-столбцам?
Рад приветствовать!
Подсказка: нужно применить динамическое программирование.
У меня создалось впечатление, что это чуть не сделал Rebbit, но что-то сорвалось...
Сложность, к которой будем стремиться, пропорциональна N^2, т.е. каждую ячейку будем просматривать только ОДИН РАЗ!
Это тоже подсказка.
P.S. Я ничего не имею против Паскаля, хотя пришлось покапаться на чердаке своей памяти, но давайте описывать алгоритм по шагам без реализации.
Цитата:
Originally posted by Green
Сложность, к которой будем стремиться, пропорциональна N^2, т.е. каждую ячейку будем просматривать только ОДИН РАЗ!
Сложность, к которой будем стремиться, пропорциональна N^2, т.е. каждую ячейку будем просматривать только ОДИН РАЗ!
Ето было бы просто чудо если б мы к ней пристемились :) Но кажется мне что ето невозможно. Всеравно придется делать цыклы третей вложености (не по исходной матрице так по другой какой). Или я ошибаюсь ???
Цитата:
Originally posted by Rebbit
Ето было бы просто чудо если б мы к ней пристемились :) Но кажется мне что ето невозможно. Всеравно придется делать цыклы третей вложености (не по исходной матрице так по другой какой). Или я ошибаюсь ???
Ето было бы просто чудо если б мы к ней пристемились :) Но кажется мне что ето невозможно. Всеравно придется делать цыклы третей вложености (не по исходной матрице так по другой какой). Или я ошибаюсь ???
Есть один алгоритм, который придумал не я, но меня методично подталкивали к нему. Пока я не конкретизировал его до конца, но сложность уже понятна, и она пропорциональна N^2.
Алгоритм состоит из несколькоих шагов, я пока проделал полтора и думаю, что их всего два.
Первый шаг очень похож на то, что представил ты, только я двигался по столбцам, а не по строкам. Если разверноуть на 90 градусов, то у меня вышло (для того же примера)следущее:
Код:
1 2 0 1
напомню, что у тебя
Код:
1 2 0 4
Цитата:
Originally posted by Green
(для того же примера)следущее:
напомню, что у тебя
(для того же примера)следущее:
Код:
1 2 0 1
напомню, что у тебя
Код:
1 2 0 4
Или я плохо описал алгоритм, или Ты ошибся при исполнении (я так понимаю исполнял вручную)
У меня получится
Код:
1 2 0 0
1 0 0
0 0
1
1 0 0
0 0
1
В етой матрице запоминается площадь белого (если он есть полностю белый) прямоугольника которий имеет кординату верхнего левого угла "х" равную номеру строчки в матрице S и толщину равную номеру столбца+1 в S. Но только ту площадь, которая лежит над строчкой и в ней (про строчки исходной матрицы).
0 в конце первой строчки потому что полоса едениц прервана "0" (я так понял 0 ето черный). Значит прямоугольник (0,0,3,0) не полностю черный.
Я уже сделал робочую програму (дома лежыт). Вечером выложу.
Но есть и лутший алгоритм. Его Grenering начала делать. Но и он не дотягивает до N^2
Цитата:
Originally posted by Green
Mоngооsе, мне кажется вся сложность и уязвимость твоего алгоритма в том, что ты сначала ищешь области, потом среди этих областей прямоугольники, а потом среди этих прямоугольников наибольший.
Mоngооsе, мне кажется вся сложность и уязвимость твоего алгоритма в том, что ты сначала ищешь области, потом среди этих областей прямоугольники, а потом среди этих прямоугольников наибольший.
Алгоритм работает не совсем так. На первом шаге определяется вся нужная информация.
Цитата:
Как будет работать твой алгоритм в случае, если все поле белое и лишь одна клеточка черная?
В зависимости от того, где расположена черная ячейка, на первом или во втором шаге двойного цикла будет выделен весь массив, и после этого сразу же выход из цикла.
После этого программа определит какие ячейки нужно проверить. В зависимости от расположения черногой ячейки, таких ячеек будет от одного до 9.
После этого для этих ячеек находится макс. прямоугольник, левым-верхним углом которым они являются. Но сколько ячеек будет реально проверено из этих макс. 9 зависит от конкретного случая.
Цитата:
Не придется ли дважды выполнять одну и ту же работу.
Это было бы глупо.
Цитата:
Кстати, по поводу алгоритмов и реализации, профессиональный программист должен четко разделять эти вещи и уметь независимо работать над ними.
Угу. Давай сосредоточимся на алгоритме и не будем переходить на личности :D
Вот моя програма. Только ето еще не реализацыя, а просто алгоритм, который можно поробовать в действии :)
Смотрите как S изменяется :)
Для етих входных даных ответ будет 6.
Если надо координаты прямоугольника - тоже не проблема.
Код:
Const N = 4;
TYPE
TArray = array[0..N-1, 0..N-1] of byte;
Const
{0 - black, 1 - white}
CM: TArray = ((1,1,0,1),
(1,1,1,1),
(0,0,1,1),
(1,0,1,1));
VAR
M, S: TArray;
i, j, line, MAX: integer;
black: boolean;
BEGIN
M := CM;
for i := 0 to N-1 do
for j := 0 to N-1-i do
S[i,j] := 0;
MAX := 0;
for line := 0 to N-1 do
for i := 0 to N-1 do
begin
black := false;
for j := 0 to N-1-i do
begin
if M[line, i+j] = 0 then black := true;
if black then
begin
if MAX < S[i, j] then MAX := S[i, j];
S[i, j] := 0;
end
else
S[i, j] := S[i, j] + j+1;
end;
end;
for i := 0 to N-1 do
for j := 0 to N-1-i do
if MAX < S[i, j] then MAX := S[i, j];
writeln(MAX);
END.
TYPE
TArray = array[0..N-1, 0..N-1] of byte;
Const
{0 - black, 1 - white}
CM: TArray = ((1,1,0,1),
(1,1,1,1),
(0,0,1,1),
(1,0,1,1));
VAR
M, S: TArray;
i, j, line, MAX: integer;
black: boolean;
BEGIN
M := CM;
for i := 0 to N-1 do
for j := 0 to N-1-i do
S[i,j] := 0;
MAX := 0;
for line := 0 to N-1 do
for i := 0 to N-1 do
begin
black := false;
for j := 0 to N-1-i do
begin
if M[line, i+j] = 0 then black := true;
if black then
begin
if MAX < S[i, j] then MAX := S[i, j];
S[i, j] := 0;
end
else
S[i, j] := S[i, j] + j+1;
end;
end;
for i := 0 to N-1 do
for j := 0 to N-1-i do
if MAX < S[i, j] then MAX := S[i, j];
writeln(MAX);
END.
Смотрите как S изменяется :)
Для етих входных даных ответ будет 6.
Если надо координаты прямоугольника - тоже не проблема.
Цитата:
Originally posted by Green
она пропорциональна N^2.
она пропорциональна N^2.
Я тут подумал над тем другим алгоритмом. Количество операций которые он виполнит зависит от входной матрицы. В найлутшем случае (когда все черное) сложность таки N^2, а в наихудшем (когда все белое) такая же как и у меня N^2*(N+1)/2.
Но он почти не нуждается в дополнительной памяти.
Кроме исходной матрицы ему нужно еще вектор на N елементов и еще так по мелочам - на временные переменные. Поскольку матрица может быть битовой, то максимальное N увеличивается в sqrt(8) раз.
Кстати мой алгоритм (смотр. выше) не нуждается в исходной матрице, ее можно подгружать с ввода по строчке. Тоесть тот же вектор на N. Только вот треугольную матрицу сум битовой не сделаеш.
Цитата:
Originally posted by Rebbit
Кстати мой алгоритм (смотр. выше) не нуждается в исходной матрице, ее можно подгружать с ввода по строчке. Тоесть тот же вектор на N. Только вот треугольную матрицу сум битовой не сделаеш.
Кстати мой алгоритм (смотр. выше) не нуждается в исходной матрице, ее можно подгружать с ввода по строчке. Тоесть тот же вектор на N. Только вот треугольную матрицу сум битовой не сделаеш.
А зачем в твоем алгоритме третий цикл?
Ладно расскажу первый шаг N^2 алгоритма:
Идем по столбцам и считаем белые клетки, при встрече черной клетки сбрасываем счетчик. Т.о. формируем матрицу NxN.
Продемонстрирую на примере:
1 1 0 1
1 1 1 1
0 0 1 1
1 0 1 1
идем по первому столбцу и формируем столбец новой матрицы:
1
2
0
1
для второго столбца
1
2
0
0
Т.о. получаем матрицу
1 1 0 1
2 2 1 2
0 0 2 3
1 0 3 4
После чего исходная матрица нам не нужна.
Думаю, что не нужно объяснять, что сложность этой операции N^2.
Для бережливых до памяти замечу, что т.к. исходная матрица далее не нужна, мы можем писать новую матрицу прямо поверх старой.
Над следующим шагом подумайте сами.
Цитата:
Originally posted by Green
Над следующим шагом подумайте сами.
Над следующим шагом подумайте сами.
Думаю алгоритм никакого секрета не представляет. Ведь как ты писал, кто-то тебе его предложил. Так что выложи. Если имеется конечно.
Цитата:
Originally posted by Mоngооsе
Думаю алгоритм никакого секрета не представляет. Ведь как ты писал, кто-то тебе его предложил. Так что выложи. Если имеется конечно.
Думаю алгоритм никакого секрета не представляет. Ведь как ты писал, кто-то тебе его предложил. Так что выложи. Если имеется конечно.
Сам алгоритм мне не предлагали, а только помогли вести ход мыслей. Кстати, я ещё сам не доконца его продумал, но там на мой взгляд остались мелочи.
Секрета в нем, конечно, нет. Просто, тема называется "Разминка для ума". Думаю, кто-то ещё желает сам дойти до решения. А может кто-то предложит более оптимаьный алгоритм.
В конце концов я, конечно, озвучу и известное мне решение.
Цитата:
Originally posted by Green
Для бережливых до памяти замечу, что т.к. исходная матрица далее не нужна, мы можем писать новую матрицу прямо поверх старой.
Для бережливых до памяти замечу, что т.к. исходная матрица далее не нужна, мы можем писать новую матрицу прямо поверх старой.
Собственно, я это и подразумевал.
Цитата:
Originally posted by Green
А зачем в твоем алгоритме третий цикл?
А зачем в твоем алгоритме третий цикл?
Он по толщине прямоугольника начало которого ровно i. Код же робочий для любой матрицы.
Кстати подозреваю что в Твоем алгоритме он (третий цыкл) тоже понадобится (только не for, а while, потому то количество операций зависит от входной матрицы)
Цитата:
Идем по столбцам и считаем белые клетки, при встрече черной клетки сбрасываем счетчик. Т.о. формируем матрицу NxN.
Ну так ведь Greenering то же сделала, только по строчам и поменяла значениями 0 и 1.
Вот здесь то и заключается динамика, а дальше, помойму, оптимизирований перебор с динамическим поиском максимальной высоты (если делать так как Green) прямоугольника. И не надо забывать о замечательной операции умножение
Цитата:
Originally posted by Rebbit
Он по толщине прямоугольника начало которого ровно i. Код же робочий для любой матрицы.
Он по толщине прямоугольника начало которого ровно i. Код же робочий для любой матрицы.
Если ты и так идешь по строке, то зачем по ней двигаться дважды?
Цитата:
Originally posted by Rebbit
Кстати подозреваю что в Твоем алгоритме он (третий цыкл) тоже понадобится (только не for, а while, потому то количество операций зависит от входной матрицы)
Кстати подозреваю что в Твоем алгоритме он (третий цыкл) тоже понадобится (только не for, а while, потому то количество операций зависит от входной матрицы)
Никакого третьего цикла:
Код:
для каждого столбца:
счетчик = 0;
для каждой строки:
если белая клетка, то счетчик++,
иначе (если черная), то счетчик=0;
записываем значение счетчика в клетку;
счетчик = 0;
для каждой строки:
если белая клетка, то счетчик++,
иначе (если черная), то счетчик=0;
записываем значение счетчика в клетку;
Цитата:
Originally posted by Rebbit
Ну так ведь Greenering то же сделала, только по строчам и поменяла значениями 0 и 1.
Ну так ведь Greenering то же сделала, только по строчам и поменяла значениями 0 и 1.
Значит, женская интуиция её не подвела, и она выбрала правильное направление, просто путь оказался длиннее, чем она предположила.
Цитата:
Originally posted by Rebbit
Вот здесь то и заключается динамика, а дальше, помойму, оптимизирований перебор с динамическим поиском максимальной высоты (если делать так как Green) прямоугольника.
Вот здесь то и заключается динамика, а дальше, помойму, оптимизирований перебор с динамическим поиском максимальной высоты (если делать так как Green) прямоугольника.
Нет. Искать нужно не максимальную высоту, а максимальную площадь, но уже по строкам.
Кстати, этот второй шаг тоже интересная подзадача.
Предлагайте алгоритмы как второго шага, так и иные для всей задачи.
Цитата:
Originally posted by Green
Если ты и так идешь по строке, то зачем по ней двигаться дважды?
Если ты и так идешь по строке, то зачем по ней двигаться дважды?
Я ведь перебираю все возможные проекции прямоугольников на строчку. Для етого line по строкам, i по началу проекции, j - по длинне проекции.
Но предлагаю забыть о моем алгоритме. Всеравно он не оптимальный. А если кто с ним не согласен, то пусть подберет вход который ево завалит :D
Цитата:
Originally posted by Green
Никакого третьего цикла:
Нет. Искать нужно не максимальную высоту, а максимальную площадь, но уже по строкам.
Никакого третьего цикла:
Код:
для каждого столбца:
счетчик = 0;
для каждой строки:
если белая клетка, то счетчик++,
иначе (если черная), то счетчик=0;
записываем значение счетчика в клетку;
счетчик = 0;
для каждой строки:
если белая клетка, то счетчик++,
иначе (если черная), то счетчик=0;
записываем значение счетчика в клетку;
Нет. Искать нужно не максимальную высоту, а максимальную площадь, но уже по строкам.
Все что я сказал про while и высоту касалось уже второво шага. While - ето цыкл по ширине прямоугольника, а максимальная висота - ето минимальное значение твоей преобразованой матрицы по всей длинне проекции на текущую строчку. Умножай длину проекции на максимальную висоту и получиш площадь. Сравниваем ее с МАКС и если надо то переприсваеваем МАКС.
Блин ето я уже чужие мисли толкаю, но всеравно ведь никто ничево лутше не предлогает.
Цитата:
Originally posted by Rebbit
Все что я сказал про while и высоту касалось уже второво шага. While - ето цыкл по ширине прямоугольника, а максимальная висота - ето минимальное значение твоей преобразованой матрицы по всей длинне проекции на текущую строчку. Умножай длину проекции на максимальную висоту и получиш площадь. Сравниваем ее с МАКС и если надо то переприсваеваем МАКС.
Блин ето я уже чужие мисли толкаю, но всеравно ведь никто ничево лутше не предлогает.
Все что я сказал про while и высоту касалось уже второво шага. While - ето цыкл по ширине прямоугольника, а максимальная висота - ето минимальное значение твоей преобразованой матрицы по всей длинне проекции на текущую строчку. Умножай длину проекции на максимальную висоту и получиш площадь. Сравниваем ее с МАКС и если надо то переприсваеваем МАКС.
Блин ето я уже чужие мисли толкаю, но всеравно ведь никто ничево лутше не предлогает.
Мой второй шаг выглядит не так.
Там тоже два цикла, как и на первом шаге:
Код:
максимальная площадь = 0;
для каждой строки:
<skip>
для каждого столбца:
<skip>
для каждой строки:
<skip>
для каждого столбца:
<skip>
Что под <skip> пока промолчу.
Green, можно я нарушу P.S. Чужие варианты (если кто знает ответ) не предлагать, только свои мысли. и розкажу етот алгоритм (тот что меня 7th научил) ???
Цитата:
Originally posted by Rebbit
Green, можно я нарушу P.S. Чужие варианты (если кто знает ответ) не предлагать, только свои мысли. и розкажу етот алгоритм (тот что меня 7th научил) ???
Green, можно я нарушу P.S. Чужие варианты (если кто знает ответ) не предлагать, только свои мысли. и розкажу етот алгоритм (тот что меня 7th научил) ???
Похоже, что мы тут одни остались.
Так что давай, рассказывай.
Может это с моим решением и не сойдется.