Далеко ** западе живут гномы, которые роют свои шахты принципиально только вниз или...

Question

Далеко на западе живут гномы, которые роют свои шахты принципиально только вниз или направо. У вас есть карта разреза земли. В скольких случаях гномов будет ждать неудача? Иными словами, сколько существует различных вариантов шахты от левого верхнего угла до правой нижней клетки, которые не содержат ни одной золотой жилы? В качестве ответа укажите одно целое число.

---

Answer 1

Составим таблицу, в которой посчитаем число путей, ведущих в данную ячейку и не содержащих ни одной жилы. 
Число путей равно сумме числа путей, ведущих в соседнюю ячейку сверху, и числа путей, ведущих в соседнюю ячейку слева, так как только из них можно попасть в текущую ячейку. В ячейки с золотом поставим нули.
Проделав вычисления, получаем ответ 106.

---