Məsələlər
Стоимость маршрута
Стоимость маршрута
На каждой клетке шахматной доски размером \textbf{8}×\textbf{8} записано целое неотрицательное число. Король может перемещаться по шахматной доске из левого нижнего угла в правый верхний, перемещаясь только вправо, вверх, или вправо-вверх. При этом стоимость прохода через данную клетку равна числу, записанному на этой клетке.
Переместите короля из левого нижнего угла в правый верхний с наименьшей стоимостью прохода.
\InputFile
На вход программе подаётся восемь строк, каждая строка содержит восемь целых неотрицательных чисел, не превосходящих \textbf{1000}. В левом нижнем углу всегда записано число \textbf{0}.
\OutputFile
В первой строке выведите единственное число - минимальную стоимость прохода из левого нижнего угла в правый верхний. Во второй строке выведите маршрут короля данной стоимости, разделяя клетки одним пробелом. Маршрут должен начинаться клеткой \textbf{a1} и заканчиваться клеткой \textbf{h8}.
Giriş verilənləri #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
Çıxış verilənləri #1
56 a1 a2 b3 c4 d5 e6 f7 g8 h8