if(matrix[y][x]==1)
m[x]++;
else
m[x]=0;
h=m[x];
Разминка для ума
Интересную задачку подкинули:
Есть клетчатое поле NxN.
Клетки этого поля могут быть белыми и черными в некотором хаотичном порядке.
Необходимо найти площадь максимального белого прямоугольника.
Цитата:
Есть клетчатое поле NxN.
Клетки этого поля могут быть белыми и черными в некотором хаотичном порядке.
Необходимо найти площадь максимального белого прямоугольника.
Ну что, кто может предложить алгоритм, а заодно и определить его асимптотическую сложность?
Кстати, может кто предложит к какой сложности надо стремится? :)
P.S. Чужие варианты (если кто знает ответ) не предлагать, только свои мысли.
Цитата:
Originally posted by Green
Чтоб не развивать опять наш минискандал, подождем устоявшегося алгоритма. :)
Чтоб не развивать опять наш минискандал, подождем устоявшегося алгоритма. :)
Так какая степень тебя устроит от размерности стороны доски? n^6? Есть мысль.
Один проход (n^2) - записываем все возможные "начала" белого прямоугольника и два параметра - максимальную его ширину и высоту.
Промежуточный итог - имеем массив только тех элементов, которые могут быть верхними левыми углами нашего клиента. Замечательно. Теперь проходим по нашему новому массиву (напр $results1[$xpos][$ypos][$width][$height]), что в среднем случае уже не n^2, a (n^2)/(10~50). И, проходя, проверяем ширину и высоту исходя из того, что меньше чем $maxfound, который пополняется, нам искать не интересно (не тратим время на лишние проверки). К концу прохода мы имеем результат.
Итого получается меньше чем полтора раза по n^2, если учесть, что n - размерность доски, т.е. квадратный корень из количества элементов.
s[][0] - стек высот;
s[][1] - счетчик повторений высоты.
Вполне может быть, что и принципиально одинаковы, да я и не утверждаю, что мое решение лучше. В твой алгоритм я особо не вникал - как уже сказал, время не всегда есть. Уж прости. Хотя с другой стороны и ты не проявил достаточного интереса, прошу прощения. i - это не более, чем указатель в стеке (или не совсем стеке, я не использовал готовых для этого способов, да и не об этом речь сейчас), h - да это просто очередная высота из массива высот. В конце строки она равна нулю (см.), т.е. условие для раскручивания стека.
Не понятен вот этот участок:
...В защиту своей реализации могу сказать, что два цикла лучше одного (IMHO) тем, что внутри них меньше условных операций.
или такой рисунок с 5-ой строки и со 2-й клетки:
В целом - так. Хотя может можно сделать раскрутку в конце строки... Конечно, получается, что твое решение, так сказать, наглядней и проще.
s[][1] - счетчик повторений высоты.
Вполне может быть, что и принципиально одинаковы, да я и не утверждаю, что мое решение лучше. В твой алгоритм я особо не вникал - как уже сказал, время не всегда есть. Уж прости. Хотя с другой стороны и ты не проявил достаточного интереса, прошу прощения. i - это не более, чем указатель в стеке (или не совсем стеке, я не использовал готовых для этого способов, да и не об этом речь сейчас), h - да это просто очередная высота из массива высот. В конце строки она равна нулю (см.), т.е. условие для раскручивания стека.
Цитата:
Это аналог моего первого шага, т.е. построение проекций:
Итерация x==n введена для раскрутки стека. Так?
Код:
Итерация x==n введена для раскрутки стека. Так?
Абсолютно. Для раскрутки в конце строки.
Цитата:
Не понятен вот этот участок:
Код:
if(h==s[0])
if(h!=0)
s[1]+=(c+1);
if(h!=0)
s[1]+=(c+1);
Да очень просто. Нет смысла итерировать счетчик нулевой высоты. Кроме того это связано с 'c'.
Цитата:
...В защиту своей реализации могу сказать, что два цикла лучше одного (IMHO) тем, что внутри них меньше условных операций.
Если выбросить вычисление высоты, то всего-то два, т.к. два последних if-а можно сделать через else. А у тебя сколько?
О 'c'.
Рассмотрим тот самый первый рисунок, начиная с 6-ой строки и 6-й клетки сразу:
Код:
проход: | условие: | i | c | стек высот / счетч.
начало 0 пуст
1 1>0 1 0 1 1
2 2>1 2 0 1,2 1,1
3 1<2(max) 1 1 1 1
3 1=1 1 1 1 1+1+1=3
4 3>1 2 0 1,3 1,1
5 1<3(max) 1 1 1 3
5 1=1 1 1 1 3+1+1=5
6 0<1(max) 0 5 пуст
начало 0 пуст
1 1>0 1 0 1 1
2 2>1 2 0 1,2 1,1
3 1<2(max) 1 1 1 1
3 1=1 1 1 1 1+1+1=3
4 3>1 2 0 1,3 1,1
5 1<3(max) 1 1 1 3
5 1=1 1 1 1 3+1+1=5
6 0<1(max) 0 5 пуст
или такой рисунок с 5-ой строки и со 2-й клетки:
Код:
-X----
-XX---
-XXX--
-XXXXX
-XXXXX
проход: | условие: | i | c | стек высот / счетч.
начало 0 пуст
1 5>0 1 0 5 1
2 4<5(max) 0 1 пуст
2 4>0 1 1 4 1+1=2
3 3<4(max) 0 2 пуст
3 3>0 1 2 3 1+2=3
4 2<3(max) 0 3 пуст
4 2>0 1 3 2 1+3=4
5 2=2 1 0 2 4+1=5
6 0<2(max) 0 5 пуст
-XX---
-XXX--
-XXXXX
-XXXXX
проход: | условие: | i | c | стек высот / счетч.
начало 0 пуст
1 5>0 1 0 5 1
2 4<5(max) 0 1 пуст
2 4>0 1 1 4 1+1=2
3 3<4(max) 0 2 пуст
3 3>0 1 2 3 1+2=3
4 2<3(max) 0 3 пуст
4 2>0 1 3 2 1+3=4
5 2=2 1 0 2 4+1=5
6 0<2(max) 0 5 пуст
В целом - так. Хотя может можно сделать раскрутку в конце строки... Конечно, получается, что твое решение, так сказать, наглядней и проще.
Цитата:
Originally posted by Dolonet
Так какая степень тебя устроит от размерности стороны доски? n^6? Есть мысль.
Один проход (n^2) - записываем все возможные "начала" белого прямоугольника и два параметра - максимальную его ширину и высоту.
Промежуточный итог - имеем массив только тех элементов, которые могут быть верхними левыми углами нашего клиента. Замечательно. Теперь проходим по нашему новому массиву (напр $results1[$xpos][$ypos][$width][$height]), что в среднем случае уже не n^2, a (n^2)/(10~50). И, проходя, проверяем ширину и высоту исходя из того, что меньше чем $maxfound, который пополняется, нам искать не интересно (не тратим время на лишние проверки). К концу прохода мы имеем результат.
Итого получается меньше чем полтора раза по n^2, если учесть, что n - размерность доски, т.е. квадратный корень из количества элементов.
Так какая степень тебя устроит от размерности стороны доски? n^6? Есть мысль.
Один проход (n^2) - записываем все возможные "начала" белого прямоугольника и два параметра - максимальную его ширину и высоту.
Промежуточный итог - имеем массив только тех элементов, которые могут быть верхними левыми углами нашего клиента. Замечательно. Теперь проходим по нашему новому массиву (напр $results1[$xpos][$ypos][$width][$height]), что в среднем случае уже не n^2, a (n^2)/(10~50). И, проходя, проверяем ширину и высоту исходя из того, что меньше чем $maxfound, который пополняется, нам искать не интересно (не тратим время на лишние проверки). К концу прохода мы имеем результат.
Итого получается меньше чем полтора раза по n^2, если учесть, что n - размерность доски, т.е. квадратный корень из количества элементов.
А изначально подразумевалось разве не общее количество замкнутых блоков операций для одной клетки? Имеется в виду то, что тут все равно придется просмотреть всю матрицу поэлементно.
Цитата:
Originally posted by REmindER
А изначально подразумевалось разве не общее количество замкнутых блоков операций для одной клетки? Имеется в виду то, что тут все равно придется просмотреть всю матрицу поэлементно.
А изначально подразумевалось разве не общее количество замкнутых блоков операций для одной клетки? Имеется в виду то, что тут все равно придется просмотреть всю матрицу поэлементно.
Ее прийдется просмотреть поэлементно полюбому, мы не можем пропустить элемент (хотя можем, конечно, но только действуя через черные методом "от противного"). Другой вопрос, как много раз мы это сделаем и сколько операций нам надо будет произвести на каждой.
Цитата:
Originally posted by Dolonet
Ее прийдется просмотреть поэлементно полюбому, мы не можем пропустить элемент (хотя можем, конечно, но только действуя через черные методом "от противного"). Другой вопрос, как много раз мы это сделаем и сколько операций нам надо будет произвести на каждой.
Ее прийдется просмотреть поэлементно полюбому, мы не можем пропустить элемент (хотя можем, конечно, но только действуя через черные методом "от противного"). Другой вопрос, как много раз мы это сделаем и сколько операций нам надо будет произвести на каждой.
Думаю, оптимальней в этом плане алгоритма Green'а не придумать, т.к. его можно свести к одному проходу.
Цитата:
Originally posted by REmindER
Думаю, оптимальней в этом плане алгоритма Green'а не придумать, т.к. его можно свести к одному проходу.
Думаю, оптимальней в этом плане алгоритма Green'а не придумать, т.к. его можно свести к одному проходу.
Один проход не всегда лучше двух. Мои полтора тоже ничего. Т.к. одни и те же клетки дважды никогда не будут проверяться. Т.е. количество проверок будет строго меньше количества клеток. Всреднем в два-четыре раза, как я могу подсчитать на сей момент. Это уже что-то.
Цитата:
Originally posted by Dolonet
Один проход не всегда лучше двух. Мои полтора тоже ничего. Т.к. одни и те же клетки дважды никогда не будут проверяться. Т.е. количество проверок будет строго меньше количества клеток. Всреднем в два-четыре раза, как я могу подсчитать на сей момент. Это уже что-то.
Один проход не всегда лучше двух. Мои полтора тоже ничего. Т.к. одни и те же клетки дважды никогда не будут проверяться. Т.е. количество проверок будет строго меньше количества клеток. Всреднем в два-четыре раза, как я могу подсчитать на сей момент. Это уже что-то.
Мне кажется, тут надо обратить внимание на то, что подразумевается под проверкой. Собственно, это зависит от алгоритма.
Если брать проверку как что-то, то вопрос в том, когда это "что-то" применить. Каким будет соотношение его внутренней сложности к сложности выборки. Тут необходима конкретизация алгоритма.
Цитата:
Originally posted by REmindER
Если брать проверку как что-то, то вопрос в том, когда это "что-то" применить. Каким будет соотношение его внутренней сложности к сложности выборки. Тут необходима конкретизация алгоритма.
Если брать проверку как что-то, то вопрос в том, когда это "что-то" применить. Каким будет соотношение его внутренней сложности к сложности выборки. Тут необходима конкретизация алгоритма.
Я предлагаю алгоритм, в котором будет естественно иерархия ифоф с глубиной, скажем, четыре вложенности (не рекурсия, конечно), и который обратится по факту проверить вообще клетка черная или белая количество раз меньшее количесва клеток примерно в полтора раза. Думаю, что быстрее ничего не придумать.
То, что я сначала написал в два прохода, делается, конечно, в один.
Цитата:
Originally posted by Dolonet
Я предлагаю алгоритм, в котором будет естественно иерархия ифоф с глубиной, скажем, четыре вложенности (не рекурсия, конечно), и который обратится по факту проверить вообще клетка черная или белая количество раз меньшее количесва клеток примерно в полтора раза. Думаю, что быстрее ничего не придумать.
То, что я сначала написал в два прохода, делается, конечно, в один.
Я предлагаю алгоритм, в котором будет естественно иерархия ифоф с глубиной, скажем, четыре вложенности (не рекурсия, конечно), и который обратится по факту проверить вообще клетка черная или белая количество раз меньшее количесва клеток примерно в полтора раза. Думаю, что быстрее ничего не придумать.
То, что я сначала написал в два прохода, делается, конечно, в один.
Не совсем понял. Нельзя ли пояснение?
Кстати, совсем необязательно пропускать итерацию нулевой высоты. Т.е. алгоритм будет таким:
Код:
s[0][0]=0;
for(y=0;y<n;y++)
{
i=0;
for(x=0;x<=n;x++)
{
c=0;
if(x==n) h=0; else
{
if(matrix[y][x]==1) m[x]++; else m[x]=0;
h=m[x];
}
if(h<s[0])
{
while(h<s[0])
{
...max s[0]*(s[1]+c)
c+=s[1];
i--;
}
}
if(h==s[0]) s[1]+=(c+1); else
{
i++;
s[0]=h;
s[1]=c+1;
};
};
};
for(y=0;y<n;y++)
{
i=0;
for(x=0;x<=n;x++)
{
c=0;
if(x==n) h=0; else
{
if(matrix[y][x]==1) m[x]++; else m[x]=0;
h=m[x];
}
if(h<s[0])
{
while(h<s[0])
{
...max s[0]*(s[1]+c)
c+=s[1];
i--;
}
}
if(h==s[0]) s[1]+=(c+1); else
{
i++;
s[0]=h;
s[1]=c+1;
};
};
};
Короче, каждый о своем... Может, эта тема уже себя изжила?
Цитата:
Originally posted by REmindER
Не совсем понял. Нельзя ли пояснение?
Не совсем понял. Нельзя ли пояснение?
Проходим по каждому элементу. Причем, естественно, не поклеточно, а диагоналями. т.е. для матрицы 10 на 10 действуем так: (1,1) (3,1) (2,2) (1,3) (5,1) (4,2) etc. если попадаем на белую клетку, то анализируем ситуацию вверх и влево с учетом того, что уже знаем.
Алгоритм достаточно непросто описать, но логика примерно такая.
Цитата:
Originally posted by REmindER
Конечно, получается, что твое решение, так сказать, наглядней и проще.
Конечно, получается, что твое решение, так сказать, наглядней и проще.
Собственно, интересует не решение, как реализация алгоритма, а сам алгоритм.
Я думаю, что предложенное тобой решение и предложенное мной решение - это один и тот же алгоритм, просто по-разному интерпретированный.
На мой взгляд, то что мы пришли к одному алгоритму с разных сторон, подчеркивает его рациональность (более точного слова не подобрал).
Mоngооsе предлагает совершенно иной вариант алгоритма. Правда пока не видно его преимуществ, т.к. не определен ещё второй шаг, а первый (IMHO) не приближает к решению.
Алгоритм Dolonet я пока не понимаю, т.к. он уж очень абстрактен.
Что касается "начал белого прямоугольника", то их действительно будет N^2, а вот возможных длин и высот только для одного такого "начала" N^3, а для всех прямоугольников в общем случае N^6.
Цитата:
Originally posted by Green
Алгоритм Dolonet я пока не понимаю, т.к. он уж очень абстрактен.
Что касается "начал белого прямоугольника", то их действительно будет N^2, а вот возможных длин и высот только для одного такого "начала" N^3, а для всех прямоугольников в общем случае N^6.
Алгоритм Dolonet я пока не понимаю, т.к. он уж очень абстрактен.
Что касается "начал белого прямоугольника", то их действительно будет N^2, а вот возможных длин и высот только для одного такого "начала" N^3, а для всех прямоугольников в общем случае N^6.
Мой алгоритм никогда не будет проверять одну и ту же клетку дважды. Т.е. спрашивать ее, черная она или белая. Поэтому n^6 тут не получается. получится меньше чем во второй в абсолютно любом случае.
Мне нарисовать схему алгоритма?
Цитата:
Originally posted by Dolonet
Мне нарисовать схему алгоритма?
Мне нарисовать схему алгоритма?
давай
Цитата:
Originally posted by Green
давай
давай
Ок. Только в понедельник, как из Дании вернусь )
В чем прикол задачи? Максимальная площадь-n*n!
Цитата: Imperator_of_RusFed
В чем прикол задачи? Максимальная площадь-n*n!
Ну а ты подумай, тема то называется "Разминка для ума".
Черных и Белых одинаковое кол-во?
А что есть претензии на дискриминацию по цвету? :D
Пардон Белых и Афроамериканских...:)
Я, признаюсь, тему не читал полностью, но может быть кого-нибудь заинтересуют мои соображения.
Я не готов дать какой-либо хороший алгоритм для решения задачи, но мне придумались две вещи, которые могут задачу несколько упростить.
Для начала, давайте будем рассматривать заданный квадрат как граф, в котором его вершины (квадратики) соединены ребрами со своими соседями, плюс к том из условия ясно, что каждая из вершин рассматриваемого графа имеет вес: либо 0, либо 1. Несложно, с помощью поиска в ширину или в глубину, выделить все области заданного квадрата, все "квадратики" в которых имели бы одинаковый вес. Если я не ошибаюсь, сложность этой операции не привысит O(N*N). Теперь поиск прямоугольников можно будет осуществлять лишь внутри конкретной области, число которых, вообще говоря, не может превысить N*N.
И о поиске. Будем считать, что все квадратики (вершины) упорядочены. Например, заданы в виде двумерного массива. При этом вершина (a_n,b_m) (n,m = 0..(N-1)) смежна с (a_{n-1},b_m), (a_{n+1},b_m), (a_n,b_{m-1}), (a_n,b_{m+1}), если таковые существуют. Давайте выберем систему счисления с основанием B большим N. Теперь в нашем графе, кроме имеющегося веса вершин (раскраска), добавим еще и другой по следующему правилу (a_n,b_m).новый_вес := (B в степени (n+1));
Теперь, стоит заметить, что какой бы мы не взяли прямоугольник составленный из квадратиков, его суммарный новый_вес будет равен cc...c0...0, т.е. будет "состоять" лишь из одних-и-те-же-цифр-а-за-ними-нулей (нули, конечно, опциальны). Просуммировав все "c" из получившейся суммы имеем площадь прямоугольника.
Я не готов дать какой-либо хороший алгоритм для решения задачи, но мне придумались две вещи, которые могут задачу несколько упростить.
Для начала, давайте будем рассматривать заданный квадрат как граф, в котором его вершины (квадратики) соединены ребрами со своими соседями, плюс к том из условия ясно, что каждая из вершин рассматриваемого графа имеет вес: либо 0, либо 1. Несложно, с помощью поиска в ширину или в глубину, выделить все области заданного квадрата, все "квадратики" в которых имели бы одинаковый вес. Если я не ошибаюсь, сложность этой операции не привысит O(N*N). Теперь поиск прямоугольников можно будет осуществлять лишь внутри конкретной области, число которых, вообще говоря, не может превысить N*N.
И о поиске. Будем считать, что все квадратики (вершины) упорядочены. Например, заданы в виде двумерного массива. При этом вершина (a_n,b_m) (n,m = 0..(N-1)) смежна с (a_{n-1},b_m), (a_{n+1},b_m), (a_n,b_{m-1}), (a_n,b_{m+1}), если таковые существуют. Давайте выберем систему счисления с основанием B большим N. Теперь в нашем графе, кроме имеющегося веса вершин (раскраска), добавим еще и другой по следующему правилу (a_n,b_m).новый_вес := (B в степени (n+1));
Теперь, стоит заметить, что какой бы мы не взяли прямоугольник составленный из квадратиков, его суммарный новый_вес будет равен cc...c0...0, т.е. будет "состоять" лишь из одних-и-те-же-цифр-а-за-ними-нулей (нули, конечно, опциальны). Просуммировав все "c" из получившейся суммы имеем площадь прямоугольника.
зы тему только нашел
Цитата: Green
Ладно расскажу первый шаг 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.
Для бережливых до памяти замечу, что т.к. исходная матрица далее не нужна, мы можем писать новую матрицу прямо поверх старой.
Над следующим шагом подумайте сами.
Идем по столбцам и считаем белые клетки, при встрече черной клетки сбрасываем счетчик. Т.о. формируем матрицу 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.
Для бережливых до памяти замечу, что т.к. исходная матрица далее не нужна, мы можем писать новую матрицу прямо поверх старой.
Над следующим шагом подумайте сами.
не понял на каком вар-те остновились
имхо в таком вар-те будет работать для размеров не больше 7х7, при большем возможны ошибочные варианты
зыы тупого перебора не избежать, если ещё актуально выложу свои соображения