Недавно я столкнулся с этим вопросом и подумал, что могу поделиться им здесь, так как не смог его получить.

Нам дают сетку 5 * 5, пронумерованную от 1-25, и набор из 5 пар точек, которые являются начальной и конечной точками пути в сетке.

Теперь нам нужно найти 5 соответствующих путей для 5 пар точек, чтобы никакие два пути не перекрывались. Также обратите внимание, что разрешены только вертикальные и горизонтальные перемещения.Также объединенная 5 дорожка должна охватывать всю сетку.

Например, нам дана пара очков:

P={1,22},{4,17},{5,18},{9,13},{20,23}

Тогда соответствующие пути будут

Что я думал до сих пор: Может быть, я смогу вычислить все пути от источника до места назначения для всех пар точек, а затем проверить, нет ли общей точки в путях. Однако это, кажется, имеет более высокую временную сложность.

Кто-нибудь может предложить лучший алгоритм? Я был бы рад, если бы можно было объяснить с помощью псевдокода. Спасибо