Цивилизация
Если кому-то сложно, то вот. Указание.
делаем обычный бфс, только при переходе в клетку добавляем 1 или 2 в зависимости от того, что в ней
Путь восстанавливаем одним из трёх способов:
Рекурсивно пока не придем в начальную клетку - вызываем ту из которой пришли, после вызова выводим букву Здесь небольшой геморрой с направлением (там же нужно вывести N S W E, а не координаты)
То же самое что и в первом, только в цикле, координаты пихаем в массив, потом, пробегаясь по массиву с конца, определяем направление и выводим
Что бы не париться с этими "с конца" можно тупо идти не из старта в финиш, а из финиша в старт, но там придётся запариться с ценой перехода между клетками, т.к. в условии прибавляем в зависимости от того что там, куда мы переходим, а в нашем случае мы считаем то, откуда мы переходим
Ребятам, которые не любят бфс и клеточки: вы можете превратить клеточки в граф и запустить алгоритм Деикстры