1) Имеется попрямоугольное поле из клеток размером, скажем, m*n. В некоторых клетках расположены числа. Все числа, кроме единиц, имеют пары, и эти пары соединяются линией;
2) Количество клеток в линии вместе с концевыми равно числам на её концах;
3) Клетки, содержащие единицы, являются папой самим себе и представляют линию длиной в одну клетку;
4) Клетки, соединяющие пары, могут преломляться по горизонтали и вертикали
5) Линии, соединяющие пары, не могут пересекаться и проходить через одну и ту же клетку.
Требуется найти и закрасить все эти линии, чтобы получить картинку.
Для 1-й, 2-х и 3-х клеток алгоритм, в принципе, понятен. Хотелось бы более или менее общий алгоритм для произвольного числа клеток.
Заранее спасибо.
Здравствуйте, slavaak, Вы писали:
S>1) Имеется попрямоугольное поле из клеток размером, скажем, m*n. В некоторых клетках расположены числа. Все числа, кроме единиц, имеют пары, и эти пары соединяются линией; S>2) Количество клеток в линии вместе с концевыми равно числам на её концах; S>3) Клетки, содержащие единицы, являются папой самим себе и представляют линию длиной в одну клетку; S>4) Клетки, соединяющие пары, могут преломляться по горизонтали и вертикали
Каждой клетке с числом k соответствует ромб из 4k-4 клеток, удалённых от неё на расстояние k-1. Среди них и нужно искать кандидатов в пару к ней.
S>5) Линии, соединяющие пары, не могут пересекаться и проходить через одну и ту же клетку.
После того, как найдены пары клеток, — решается задача, похожая на задачу о разводке печатной платы.
S>Требуется найти и закрасить все эти линии, чтобы получить картинку.
Это что, новая версия японского кроссворда? Или есть какое-то практическое применение?
S>Для 1-й, 2-х и 3-х клеток алгоритм, в принципе, понятен. Хотелось бы более или менее общий алгоритм для произвольного числа клеток.
Сдаётся мне, даже для поля, содержащего только числа 1 и 2, получается NP-полная задача. А именно, это задача о построении гамильтонова пути в графе.
Впрочем, надо тщательно поразмыслить.
Здравствуйте, Кодт, Вы писали: К>Каждой клетке с числом k соответствует ромб из 4k-4 клеток, удалённых от неё на расстояние k-1. Среди них и нужно искать кандидатов в пару к ней.
Ты не прав. Я могу и буквой П пойти. Условия "кратчайшности" расстояния не было.
К>Сдаётся мне, даже для поля, содержащего только числа 1 и 2, получается NP-полная задача. А именно, это задача о построении гамильтонова пути в графе. К>Впрочем, надо тщательно поразмыслить.
Я бы так не сказал.
Поллиномиальное решение для чисел 1 и 2:
Покрасим доску шахматной расскраской. Задача свелась к нахождению для каждой черной двойки пары из белых двоек. Это задача поиска совершенного паросочетания в двудольном графе, которая успешно решается за полиномиальное время (есть простой алгоритм за O(N^3) и более сложные за меньшую асимптотику)
Я думаю в описанную схему можно включить и тройки... но когда появятся более большие числа... боюсь эффективного решения не найти.
Здравствуйте, Tan4ik, Вы писали:
К>>Каждой клетке с числом k соответствует ромб из 4k-4 клеток, удалённых от неё на расстояние k-1. Среди них и нужно искать кандидатов в пару к ней. T>Ты не прав. Я могу и буквой П пойти. Условия "кратчайшности" расстояния не было.
Блин! Недочитал.
К>>Сдаётся мне, даже для поля, содержащего только числа 1 и 2, получается NP-полная задача. А именно, это задача о построении гамильтонова пути в графе. К>>Впрочем, надо тщательно поразмыслить. T>Я бы так не сказал. T>Поллиномиальное решение для чисел 1 и 2: T>Покрасим доску шахматной расскраской. Задача свелась к нахождению для каждой черной двойки пары из белых двоек. Это задача поиска совершенного паросочетания в двудольном графе, которая успешно решается за полиномиальное время (есть простой алгоритм за O(N^3) и более сложные за меньшую асимптотику)
А, точно. Почему-то я подумал в сторону не просто "замостить поле доминошками", но и чтобы это была "доминошная партия".
T>Я думаю в описанную схему можно включить и тройки... но когда появятся более большие числа... боюсь эффективного решения не найти.
Всё равно остался открытым вопрос о физическом смысле этой задачи. Может, там вовсе не нужно решать её...
Перекуём баги на фичи!
