eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Стоимость маршрута

Стоимость маршрута

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

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

Переместите короля из левого нижнего угла в правый верхний с наименьшей стоимостью прохода.

Входные данные

На вход программе подаётся восемь строк, каждая строка содержит восемь целых неотрицательных чисел, не превосходящих 1000. В левом нижнем углу всегда записано число 0.

Выходные данные

В первой строке выведите единственное число - минимальную стоимость прохода из левого нижнего угла в правый верхний. Во второй строке выведите маршрут короля данной стоимости, разделяя клетки одним пробелом. Маршрут должен начинаться клеткой a1 и заканчиваться клеткой h8.

Пример

Входные данные #1
9 9 9 9 9 9 1 9
9 9 9 9 9 1 9 2
9 9 9 9 9 9 1 9
9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9
0 9 9 9 9 9 9 9
Выходные данные #1
56
a1 a2 b3 c4 d5 e6 f7 g8 h8