Задача №114303. Любопытная черепаха
Как известно, черепахи любят ходить по двумерному полю из левого верхнего угла в правый нижний кратчайшим путём, перемещаясь в соседние по стороне клетки. Дана двумерная таблица из нулей и единиц - модель поля, по которому ходит черепаха. Единицей обозначается участок с достопримечательностями, а нулем - без них.
Черепаха хочет пройти от начальной клетки своего пути до конечной, обязательно посетив хотя бы одну достопримечательность - клетку, обозначенную единицей.
Вам требуется написать программу, которая определит, сколько существует кратчайших путей из левого верхнего угла в правый нижний, проходящих хотя бы через одну единицу.
В первой строке входных данных даны целые числа \(n\) и \(m\) (\(1 \le n, m \le 30\)) - количество строк и столбцов в таблице. Следующие \(n\) строк по \(m\) чисел содержат целые числа \(a_{i, j}\) (\(0 \le a_{i, j} \le 1\)) - элементы таблицы, задающие клетки поля.
Напоминаем, что два числа из одной строки в языке Python можно считать так: n, m = map(int, input().split())
Выведите одно число --- количество подходящих кратчайших путей.
Во втором примере черепаха начинает свой путь с клетки с достопримечательностью, поэтому все пути ей подходят. То же касалось бы и конечной клетки.
3 4 0000 0100 0010
8
2 2 10 00
2