В таблице N*N, где N<15, клетки заполнены случайным образом цифрами от 0 до 9. Найти маршрут из клетки А(1,1) в клетку А(N,N) такой, что:

1) маршрут состоит из отрезков, соединяющих центры клеток, имеющих общую сторону;

2) длина маршрута минимальна;

3) сумма цифр, встречающихся на маршруте, максимальна.