Дана матрица MxN. Для каждой клетки матрицы задан её цвет -- чёрный или белый. Одноцветная область -- это связное множество клеток одного цвета (т. е. для любой пары клеток этого множества существует путь между ними, состоящий из клеток этого множества, такой, что соседние клетки в нём имеют общую сторону), не содержащееся в другом таком множестве. Мы можем делать следующее действие: выбрать произвольную одноцветную область и поменть цвет всех её клеток. Соотвественно появятся другие одноцветные области. Определить минимальное количество действий, за которое всю матрицу можно сделать одноцветной (полностью белой или чёрной).
Для простоты возьмем M=N.
Если просто гнать волну из каждой клетки, получим O(N^4).
следующее:
К>1) строится граф, где каждая сплошная область — это вершина, а стыки областей — рёбра К>2) находится диаметр графа (наибольший из кратчайших путей между всеми вершинами); если диаметров много, берём любой К>3) находится серединная вершина на этом диаметре; если длина D диаметра чётная, берём любую из двух
Это хорошо подходит для ковров с большими пятнами.
Но для раскраски, близкой к шахматной, имеем граф с O(N^2) вершин и O(N^2) ребер.
Поиск кратчайших путей между всеми вершинами (с применением Дейкстры со всякими наворотами) потребует как минимум O(N^4) времени.
Кроме того, для хранения расстояний надо O(N^4) памяти, а это не вписывается в ограничения задачи.
Здравствуйте, Трурль, Вы писали:
Т>Это хорошо подходит для ковров с большими пятнами. Т>Но для раскраски, близкой к шахматной, имеем граф с O(N^2) вершин и O(N^2) ребер. Т>Поиск кратчайших путей между всеми вершинами (с применением Дейкстры со всякими наворотами) потребует как минимум O(N^4) времени. Т>Кроме того, для хранения расстояний надо O(N^4) памяти, а это не вписывается в ограничения задачи.
Т>Нет ли еще какого способа?
Нет необходимости использовать Дейкстру, как и явно хранить расстояния между каждой парой вершин.
В данном случае все ребра имеют вес 1, поэтому достаточно выполнить N^2 поисков в ширину от каждой вершины.
Оценка по времени не меняется (O(N^4)), а по памяти уже O(N^2).
Здравствуйте, diver_ru, Вы писали:
_>Нет необходимости использовать Дейкстру, как и явно хранить расстояния между каждой парой вершин. _>В данном случае все ребра имеют вес 1, поэтому достаточно выполнить N^2 поисков в ширину от каждой вершины. _>Оценка по времени не меняется (O(N^4)), а по памяти уже O(N^2).
С этого я, собственно, и начинал Т>>Если просто гнать волну из каждой клетки, получим O(N^4).
Не хватает скорости-то.
Здравствуйте, Трурль, Вы писали:
Т>Нет ли еще какого способа?
Можно найти диаметр и за линейное время от размера поля. Будем сжимать поле с краев, т.е:
1) добавим в очередь все вершины, соответствующие областям, которые касаются краев поля
2) делаем BFS, отталкиваясь от вершин в очереди
3) количество итераций bfsа = диаметру, последняя выброшенная из очереди вершина — центр
Здравствуйте, mehas, Вы писали:
M>Здравствуйте, Трурль, Вы писали:
Т>>Нет ли еще какого способа?
M>Можно найти диаметр и за линейное время от размера поля. Будем сжимать поле с краев, т.е:
M>1) добавим в очередь все вершины, соответствующие областям, которые касаются краев поля M>2) делаем BFS, отталкиваясь от вершин в очереди M>3) количество итераций bfsа = диаметру, последняя выброшенная из очереди вершина — центр
Это неверно. Например, на таком тесте алгоритм даст 1, а должно быть 2:
Здравствуйте, Vintik_69, Вы писали:
V_>Здравствуйте, mehas, Вы писали:
M>>Здравствуйте, Трурль, Вы писали:
Т>>>Нет ли еще какого способа?
M>>Можно найти диаметр и за линейное время от размера поля. Будем сжимать поле с краев, т.е:
M>>1) добавим в очередь все вершины, соответствующие областям, которые касаются краев поля M>>2) делаем BFS, отталкиваясь от вершин в очереди M>>3) количество итераций bfsа = диаметру, последняя выброшенная из очереди вершина — центр
V_>Это неверно. Например, на таком тесте алгоритм даст 1, а должно быть 2: V_>
010
V_>101
V_>010
Мда, точно.
ну, по крайней мере можно сократить до O(N^3), если пустить BFSы только от крайних областей и выбрать максимум.
Здравствуйте, Трурль, Вы писали:
Т>Здравствуйте, Pro100Oleh, Вы писали:
PO>>Было бы неплохо упомянуть эти ограничения.
Т>N <= 100, памяти — 64М, времени — 2с на неизвестнокакой машине.
Дана матрица MxN. Для каждой клетки матрицы задан её цвет -- чёрный или белый. Одноцветная область -- это связное множество клеток одного цвета (т. е. для любой пары клеток этого множества существует путь между ними, состоящий из клеток этого множества, такой, что соседние клетки в нём имеют общую сторону), не содержащееся в другом таком множестве. Мы можем делать следующее действие: выбрать произвольную одноцветную область и поменть цвет всех её клеток. Соотвественно появятся другие одноцветные области. Определить минимальное количество действий, за которое всю матрицу можно сделать одноцветной (полностью белой или чёрной).
Т>Для простоты возьмем M=N. Т>Если просто гнать волну из каждой клетки, получим O(N^4).
Т>Кодт предложил
следующее:
К>>1) строится граф, где каждая сплошная область — это вершина, а стыки областей — рёбра К>>2) находится диаметр графа (наибольший из кратчайших путей между всеми вершинами); если диаметров много, берём любой К>>3) находится серединная вершина на этом диаметре; если длина D диаметра чётная, берём любую из двух
Т>Это хорошо подходит для ковров с большими пятнами. Т>Но для раскраски, близкой к шахматной, имеем граф с O(N^2) вершин и O(N^2) ребер. Т>Поиск кратчайших путей между всеми вершинами (с применением Дейкстры со всякими наворотами) потребует как минимум O(N^4) времени. Т>Кроме того, для хранения расстояний надо O(N^4) памяти, а это не вписывается в ограничения задачи.
Т>Нет ли еще какого способа?
Вообще говоря, оценка O(N^4) не совсем логична, потому как сбивает с толку, вроде как получается очень тяжелый алогоитм. Точнее будет оценивать по количеству элементов матрицы MN.
Задача имеет линейный алгоритм решения O(2MN) в худшем случае и требует дополнительной памяти RAM(2MN) для нижеприведенного алгоритма (если сделать бинарно — еще меньше). Но можно еще уменьшить коэффициент 2, снижаясь до линейного (дальше оптимизировать просто влом ).
Основная идея проста — минимальное число заливок будет определяться половиной максимального пути по "зебре" областей от угла матрицы (с учетом четности). Достаточно пройти волновым методом по всем элементам единожды, сосчитав число зон.
// Initialize#define BLACK 0x80000000 // black element#define WHITE 0x00000000 // white element#define WAVED 0x7fffffff // inner element
// select near not waved element and define as current wave element or check for boundary element of new wave#define CHSET(a) if (!(Carpet[a] & WAVED)) { if ((Carpet[a] & BLACK)==B) { Carpet[a] ^= W; Carpet[a] ^= BLACK; AStack.Push(a); } \
else { bBound = true; } }
const unsigned __int32 M = 3;
const unsigned __int32 N = 5;
const unsigned __int32 P = M*N;
unsigned __int32 Carpet[P];
// Set Carpet (example)for (unsigned __int32 i = 0; i<P; i++)
Carpet[i] = i & 0x01 ? WHITE : BLACK;
// Get maximal black-white path by stack optimized wave method (most worst O(2MN); M(2MN))
Stack AStack;
Stack BStack;
R__ASSERT(AStack.Initialize(P)); // current wave elements holder
R__ASSERT(BStack.Initialize(P)); // current wave boundary elements holderunsigned __int32 Path = 0; // path lengthunsigned __int32 W = 1; // first wave indexunsigned __int32 B = Carpet[0] & BLACK; // current wave color
Carpet[0] |= W; // set first element as waved
AStack.Push(0); // start from Carpet[0] elementunsigned __int32 S; // number of boundary elementsdo// for each semicolor wave
{
do// for each element of semicolor wave
{
bool bBound = false; // boundary elementunsigned __int32 C = AStack.Pop(); // current element of waveunsigned __int32 R = C%N; // row of element in matrix (M;N)if (C>N) CHSET(C-N); // check and set up near elementif ((C+N)<P) CHSET(C+N); // check and set down near elementif (R>0) CHSET(C-1); // check and set left near elementif ((R+1)<N) CHSET(C+1); // check and set right near elementif (bBound) BStack.Push(C); // save boundary element
} while(AStack.Size()); // continue until have new elements of current wave
S = BStack.Size(); // number of new boundary elementsfor (unsigned __int32 i = 0; i<S; i++) // for each new boundary element
{
unsigned __int32 C = BStack.Pop(); // get boundary element
Carpet[C] ^= BLACK; // change color
AStack.Push(C); // save as new wave element
}
Path++; // increase path
W++; // increase wave index
B ^= BLACK; // change wave color
} while(S); // continue until have new boundary elements
Path--; // remove last path
Path = (Path>>0x01) + (Path & 0x01); // minimal number of color swaps for full painting
Здесь класс Stack — просто хранилище int с небольшим функционалом: Push, Pop, Size — число заданных элементов.
Стек A — хранит элементы текущей области, стек B — граничные элементы текущей области, чтобы не проходить все элементы заново.
Коэффициент 2 в сложности появляется в худших случаях, когда матрица поделена на зоны толщиной в один элемент — шахматная доска или зебра и т.п.
Здравствуйте, Razard, Вы писали:
R>Основная идея проста — минимальное число заливок будет определяться половиной максимального пути по "зебре" областей от угла матрицы (с учетом четности).
Здравствуйте, Трурль, Вы писали:
Т>Здравствуйте, Razard, Вы писали:
R>>Основная идея проста — минимальное число заливок будет определяться половиной максимального пути по "зебре" областей от угла матрицы (с учетом четности).
Т>А вот это не очевидно.
Как раз вполне очевидно, однако не для угла матрицы, поскольку чтобы получить минимум заливок требуется начать с области, которая равноудалена от максимально удаленных областей.
С учетом того, что в разных направлениях может быть разное по четности число шагов, в таких случаях нужно прибавить единицу.
Проблема в другом — решал ночью и протормозил, что начальная точка из угла матрицы абсолютно произвольно удалена от центральной и крайних областей.
Поэтому сначала нужно определить одну из наиболее удаленных областей. А это решаемо из любой точки матрицы. Объясню почему:
— Если начальная точка относится к центальной — очевидно, мы прийдем в наиболее удаленную область.
— Если начальная точка относится к наиболее удаленной области от центра — мы прийдем в другую наиболее удаленную от центра область.
— Если же начальная точка относится к какой-либо промежуточной области — мы также прийдем в какую-либо наиболее удаленную от центра область, просто "потеряв"
несколько шагов второго варианта, как если бы стартовали из какой-либо наиболее удаленной области.
На втором этапе получаем максимальный путь, который равен сумме минимальных путей из центральной области (опять же, с учетом четности двух разных направлений).
Правильный код O(4MN), но сводящийся к O(2MN):
// Initialize#define BLACK 0x80000000 // black element#define WHITE 0x00000000 // white element#define WAVED 0x00000001 // inner element
// select near not waved element and define as current wave element or check for boundary element of new wave#define CHSET1(a) if (!(Carpet[a] & WAVED)) { if ((Carpet[a] & BLACK)==B) { Carpet[a] ^= WAVED; Carpet[a] ^= BLACK; AStack.Push(a); } \
else { bBound = true; } }
#define CHSET2(a) if (Carpet[a] & WAVED) { if ((Carpet[a] & BLACK)==B) { Carpet[a] ^= WAVED; Carpet[a] ^= BLACK; AStack.Push(a); } \
else { bBound = true; } }
const unsigned __int32 M = 7;
const unsigned __int32 N = 7;
const unsigned __int32 P = M*N;
unsigned __int32 Carpet[P];
// Set Carpet (example)for (unsigned __int32 i = 0; i<P; i++)
Carpet[i] = i & 0x01 ? WHITE : BLACK;
// Get maximal black-white path by stack optimized wave method (most worst O(2MN); M(2MN))
Stack AStack;
Stack BStack;
R__ASSERT(AStack.Initialize(P)); // current wave elements holder
R__ASSERT(BStack.Initialize(P); // current wave boundary elements holderunsigned __int32 Path = 0; // path lengthunsigned __int32 B = Carpet[0] & BLACK; // current wave colorunsigned __int32 C; // current element of wave
Carpet[0] |= WAVED; // set first element as waved
AStack.Push(0); // start from Carpet[0] elementunsigned __int32 S; // number of boundary elements
// get last waved elementdo// for each semicolor wave
{
do// for each element of semicolor wave
{
bool bBound = false; // boundary element
C = AStack.Pop(); // current element of waveunsigned __int32 R = C%N; // row of element in matrix (M;N)if (C>N) CHSET1(C-N); // check and set up near elementif ((C+N)<P) CHSET1(C+N); // check and set down near elementif (R>0) CHSET1(C-1); // check and set left near elementif ((R+1)<N) CHSET1(C+1); // check and set right near elementif (bBound) BStack.Push(C); // save boundary element
} while(AStack.Size()); // continue until have new elements of current wave
S = BStack.Size(); // number of new boundary elementsfor (unsigned __int32 i = 0; i<S; i++) // for each new boundary element
{
unsigned __int32 C = BStack.Pop(); // get boundary element
Carpet[C] ^= BLACK; // change color
AStack.Push(C); // save as new wave element
}
B ^= BLACK; // change wave color
} while(S); // continue until have new boundary elements
// get maximal path
AStack.Push(C); // push last waved elementdo// for each semicolor wave
{
do// for each element of semicolor wave
{
bool bBound = false; // boundary element
C = AStack.Pop(); // current element of waveunsigned __int32 R = C%N; // row of element in matrix (M;N)if (C>N) CHSET2(C-N); // check and set up near elementif ((C+N)<P) CHSET2(C+N); // check and set down near elementif (R>0) CHSET2(C-1); // check and set left near elementif ((R+1)<N) CHSET2(C+1); // check and set right near elementif (bBound) BStack.Push(C); // save boundary element
} while(AStack.Size()); // continue until have new elements of current wave
S = BStack.Size(); // number of new boundary elementsfor (unsigned __int32 i = 0; i<S; i++) // for each new boundary element
{
unsigned __int32 C = BStack.Pop(); // get boundary element
Carpet[C] ^= BLACK; // change color
AStack.Push(C); // save as new wave element
}
Path++; // increase path
B ^= BLACK; // change wave color
} while(S); // continue until have new boundary elements
// calculate maximal path
Path = (Path>>0x01) + (Path & 0x01); // minimal number of color swaps for full painting
).