Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение
одну из двух команд: вправо или вниз. По команде вправо Робот
перемещается в соседнюю правую клетку, по команде вниз – в
соседнюю нижнюю. При попытке пересечь границы квадрата
(внутренние, обозначенные жирной линией, или внешние) Робот
разрушается. В каждой клетке квадрата записано одно из двух чисел:
0 или 1 Если в клетке записано число 1, Робот может попасть в эту
клетку, а если в клетке записано число 0, то робот не может попасть
в такую клетку. Определите количество , которыми Робот
может попасть из левой верхней клетки в правую нижнюю. В ответе
укажите искомое число.
Перед тем, как начать решение задачи, давайте создадим двумерный список размером N×N, где будем хранить информацию о том, из скольких клеток можно попасть в текущую клетку. Для этого каждой клетке, в которую можно попасть, присвоим значение 1. А каждой клетке, в которую нельзя попасть или которая выходит за границы квадрата, присвоим значение 0.
Начнем заполнять список с первой строки и первого столбца. Так как из левой верхней клетки можно попасть только в нее саму, то присвоим ей значение 1. Заполним также первый столбец, идя сверху вниз. Если текущая клетка имеет значение 1 и предыдущая клетка в столбце (то есть клетка сверху) также имеет значение 1, то в текущую клетку можно попасть только из предыдущей клетки столбца. Значение текущей клетки будет равно значению предыдущей клетки столбца. В противном случае, если текущая клетка имеет значение 1 и предыдущая клетка в столбце имеет значение 0, значит, в текущую клетку нельзя попасть из столбца. Присваиваем ей значение 0.
После заполнения первой строки и первого столбца, будем заполнять оставшиеся ячейки списка, двигаясь слева направо и сверху вниз. Если текущая клетка имеет значение 1, то количество путей до нее будет равно сумме количества путей до клетки, расположенной слева от нее, и количества путей до клетки, расположенной сверху. Если текущая клетка имеет значение 0, то количество путей до нее будет равно 0 (так как в нее нельзя попасть).
После того, как список будет полностью заполнен, значение в правой нижней клетке будет искомым количеством путей, которыми Робот может попасть из левой верхней клетки в правую нижнюю.
Надеюсь, я смог максимально подробно и обстоятельно объяснить решение данной задачи. Если у вас остались вопросы, буду рад на них ответить.