Задание 18. Робот на клетчатом поле

Квадрат разлинован на 22 × 22 клеток, в каждой лежит монета достоинством от 1 до 100 (файл b18-2.txt, строки поля через табуляцию). Робот идёт из левой верхней клетки в правую нижнюю, за один шаг перемещаясь вправо, вниз или по диагонали вправо-вниз, и собирает монеты из всех клеток, где побывал, включая начальную и конечную. Найди наибольшую и наименьшую возможные суммы. Запиши два числа через пробел.

Квадрат разлинован на 9 × 9 клеток, в каждой лежит монета достоинством от 1 до 100. Файл b18-w2.txt: в первой строке N, дальше N строк монет, потом стены: «R i j» значит стена справа от клетки в строке i и столбце j, «D i j» стена снизу (нумерация с 1), край поля тоже стена. Робот начинает в левой верхней клетке и ходит только вправо или вниз, сквозь стены не проходит. Он останавливается в клетке, у которой стена и справа, и снизу. Найди наибольшую и наименьшую сумму монет, которую робот может собрать (включая начальную и конечную клетки). Запиши два числа через пробел.

Квадрат разлинован на 20 × 20 клеток, в каждой лежит монета достоинством от 1 до 100 (файл b18-5.txt, строки поля через табуляцию). Робот идёт из левой верхней клетки в правую нижнюю, за один шаг перемещаясь вправо, вниз или по диагонали вправо-вниз, и собирает монеты из всех клеток, где побывал, включая начальную и конечную. Найди наибольшую и наименьшую возможные суммы. Запиши два числа через пробел.