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

Question

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

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

Answer 1

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

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

---

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

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

Answer 2

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