Создать алгоритм заполнения игрового поля?

Question

[Николай Кавуненко]

Приветствую!

Не могу справиться с задачей — может хабросообщество подскажет в каком направлении смотреть.

Есть игровое поле n на m клеток.

На нем выставляем x пар фигур (допустим, в случайном порядке).

Задача алгоритма — соединить пары фигур линиями, которые проходят по свободным клеткам (по диагонали клетки соединять нельзя) таким образом, чтобы на поле не осталось пустых клеток. Или сказать, что для данной расстановки фигур решения нет.

Соединительные линии не могут пересекаться.

Может кто встречал подобную задачу на олимпиадах или еще где.

Буду благодарен за любые подсказки =)

Comments

[TheHorse]

Фигура = одна клетка? Как много может быть фигур? какого размера может быть поле? ограничения по памяти, времени?

[Николай Кавуненко]

Да, фигура занимает одну клетку. Пара фигур -> две клетки. Ограничение по фигурам — это min из n и m
На память и время ограничение разумности.
Т.е. задача не одно поле решить, а около 100 000 полей размерами от 5х5 до 10х10.
И желательно, чтобы алгоритм это осилил за пару суток.
Примерно так.

[Assorium]

Прости за оффтоп, уж не аналог Flow Free (Android) решил создать?

[Николай Кавуненко]

Посмотрел. Что-то похожее, но задача совсем другая.

Answer 1

[Андрей]

Я бы смотрел в сторону поиска путей. Алгоритмов множество — A* (A star), волновой и т.д. Лично у меня имеется опыт волнового алгоритма — в реализации довольно простой. А* в свое время осилить не смог.
Рассчитываете «расстояние» между точками, и начинаете от самых близких друг к другу. Как только построили путь — эти точки(клетки), которые в него входят, более не доступны при расчете для следующего пути. Полную заполняемость поля можно добиться «играясь» с кол-вом точек.

Answer 2

[Muff]

Похоже на задачу трассировки печатных плат.

Answer 3

[afiskon]

Похоже на задачу для A*. Вот, надеюсь, поможет: eax.me/a-star/