Задача, которая сделала правило Варнсдорфа широко известным. Но старожилы знают, что раньше формулировка задачи была другой. Давайте посмотрим, как она звучит сейчас:
В первоначальной формулировке задачи на поле могли быть стенки, через которые конь мог перепрыгнуть, но на которые не мог вставать (отсюда осталось наследие во входных данных, из которых, по факту, нужна лишь позиция буквы "K").
Правило Варнсдорфа гласит, что при обходе доски коню надо следовать в то поле, из которого существует минимальное число ходов.
И благодаря этой задаче выяснилось, что на произвольном поле всё равно возможны заходы в тупики, и в общем случае это правило не помогает. Поэтому задачу привели к классическому виду - в качестве доски выступает произвольный прямоугольник.
Но при такой формулировке правила возможна неоднозначность: в какую клетку следует идти, если существует несколько достижимых клеток с минимальным значением? Если зафиксировать какой-то порядок, то появятся единичные случаи входных данных, при которых конь будет долго гулять по доске. В этом месте нам поможет рандом. Давайте разбираться по ходу дела.
Определим несколько глобальных переменных для простоты: размеры поля, само поле, флаг того, что ответ не найден, и все восемь возможных перемещений шахматного коня.
Ещё с помощью define переопределили x и y, чтобы сократить запись при работе с pair.
Считаем входные данные. Здесь нет ничего необычного, лишь используем барьерный метод: вокруг доски оставляем полосу шириной в две клетки из -1, чтобы не делать проверки, что конь не вышел за границы доски. Так мы уменьшим размер кода и константу.
Обходить доску будем рекурсивной функцией, которая на вход принимает координаты клетки, в которой сейчас стоит конь и номер текущего хода.
Первым делом рекомендую в рекурсии писать условие выхода из неё. В нашем случае всё просто: если номер хода совпадает с размером доски, значит можно вывести поле, пометить, что ответ найден и выйти из функции.
Дальше нам надо проверить всех соседей текущей клетки и посчитать их соседей, в которые можно сходить (по правилу Варнсдорфа). Для каждого соседа в вектор положим пару: количество его "хороших" соседей и номер клетки в порядке, перечисленном в dd.
После этого выбираем минимальное значение в получившемся векторе и вызываемся рекурсивно от этой клетки.
Если рекурсия не нашла ответ, то надо вернуть поле в исходное состояние (которое мы изменили в строке 19), поэтому в 41ой строке зануляем текущую клетки перед откатом назад, чтобы на новой ветке рекурсивного обхода мы могли зайти в текущую клетку.
Внимательный читатель заметил, что в этом коде всегда выбирается первое минимальное значение в порядке, заданном в векторе dd. А значит существуют варианты полей, для которых обход не будет находить обход.
Чтобы исправить эту несправедливость, просто запустим наш обход несколько раз для произвольных порядков переходов в dd.
Так легко и непринуждённо мы решили задачу на 71% сложности.
Предыдущий выпуск: Задача 717. Производство деталей
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.