Соответствует алгоритм поиска пар?

Question

Я нашел интересную игру с парным совпадением в http://xepthu.uhm.vn. Правило простое, вы должны найти и соединить двух одинаковых покемонов, но путь между ними не заблокирован и направление не может быть изменено 3 раза , Давайте посмотрим пример:

Я много думаю об алгоритме, чтобы проверить, допустим ли путь между любыми двумя выбранными покемонами, но потому что я новичок, поэтому я не могу найти никакого решения. Можете ли вы предложить мне один в C #?

Answer 1

Это в основном проблема поиска пути из теории графов . Поля в сетке являются узлами, а все смежные поля связаны ребром.

Поиск пути - хорошо известная проблема, и существует множество алгоритмов, которые решают эту проблему. Поскольку ваш график довольно мал, лучшее решение здесь, вероятно, просто алгоритм грубой силы. Популярным алгоритмом поиска пути является алгоритм Дейкстры .

---

Грубая сила: Начните с какого-нибудь покемона и исследуйте все возможные способы, чтобы увидеть, ведет ли он к идентичным покемонам. Вы можете прекратить исследование пути, если путь заблокирован или имеет более 2 поворотов.

Вам понадобится некоторый «указатель», указывающий на поле в сетке. Указатель может перемещаться влево, вправо, вверх или вниз при условии, что поле в этом направлении не заблокировано. Переместите указатель на соседнее поле. Помните, откуда вы пришли и сколько оборотов вы сделали. Повторяйте это, пока не дойдете до пункта назначения. Вернитесь назад, если количество ходов достигнет 3. Убедитесь, что вы не бегаете кругами.

Answer 2

Посмотрите на плоские графики. Вам нужно будет ввести второе условие: можно пройти не более четырех узлов (начальный узел - первое изменение направления - второе изменение направления - конечный узел).