Две дополнительные задачи

В этих задачах лабиринт не зациклен, т.е. из верхних клеток нельзя ходить вверх, из левых - влево, и т.д.

ZA: Прямоугольный лабиринт

Лабиринт представляет собой прямоугольник, разбитый на клетки. Некоторые из клеток заняты каменными глыбами (через них ходить нельзя). Кладоискатель может перемещаться из клетки, где он находится, в любую соседнюю по горизонтали или вертикали (если там нет каменной глыбы).

Изначально кладоискатель находится в левой верхней клетке лабиринта.

Клад находится в правой нижней клетке лабиринта.

Определите минимальную длину пути кладоискателя до клетки с кладом.

Входные данные
Заданы сначала числа N и M (не превышающие 10) - размеры лабиринта. Затем задана карта лабиринта - N строк по M чисел в каждой. Число 0 обозначает свободную клетку. Число 1 - занятую. Числа разделяются пробелами.

Выходные данные
Выведите одно число - минимальную длину пути из левой верхней клетки в правую нижнюю. Гарантируется, что путь существует.

5 6
0 0 0 0 0 0
1 1 1 1 0 1
0 0 0 0 0 1
0 1 1 1 1 1
0 0 0 0 0 0

17

ZB: Пути до единиц

Вам дана табличка, состоящая из N строк и M столбцов. В каждой клетке таблицы стоит либо 0, либо 1. Расстоянием между клетками (x1,y1) и (x2,y2) называется |x1-x2|+|y1-y2|. Вам нужно построить другую таблицу, в которой в каждой клетке стоит расстояние от данной до ближайшей клетки, содержащей 1 (в начальной таблице). Гарантируется, что хотя бы одна 1 в таблице есть.

Входные данные
В первой строке вводятся два натуральных чисал, не превосходящих 100 - N и M. Далее идут N строк по M чисел - элементы таблицы.

Выходные данные
Выведите N строк по M чисел - элементы искомой таблицы.

2 3
0 0 1
1 0 0

1 1 0
0 1 1