Не могу справиться с задачей — может хабросообщество подскажет в каком направлении смотреть.
Есть игровое поле n на m клеток.
На нем выставляем x пар фигур (допустим, в случайном порядке).
Задача алгоритма — соединить пары фигур линиями, которые проходят по свободным клеткам (по диагонали клетки соединять нельзя) таким образом, чтобы на поле не осталось пустых клеток. Или сказать, что для данной расстановки фигур решения нет.
Соединительные линии не могут пересекаться.
Может кто встречал подобную задачу на олимпиадах или еще где.
Да, фигура занимает одну клетку. Пара фигур -> две клетки. Ограничение по фигурам — это min из n и m
На память и время ограничение разумности.
Т.е. задача не одно поле решить, а около 100 000 полей размерами от 5х5 до 10х10.
И желательно, чтобы алгоритм это осилил за пару суток.
Примерно так.
Я бы смотрел в сторону поиска путей. Алгоритмов множество — A* (A star), волновой и т.д. Лично у меня имеется опыт волнового алгоритма — в реализации довольно простой. А* в свое время осилить не смог.
Рассчитываете «расстояние» между точками, и начинаете от самых близких друг к другу. Как только построили путь — эти точки(клетки), которые в него входят, более не доступны при расчете для следующего пути. Полную заполняемость поля можно добиться «играясь» с кол-вом точек.
Простой
