SPOJ in Gyumri

   Задан лабиринт, который описывается матрицей размера NxN. В левой верхней комнате (координаты [1;1]) находится робот, который может двигаться в 2 направления - юг и восток (низ и право). Каждая комната в лабиринте имеет номер. Задача робота добраться в правую нижнюю комнату (координаты [N;N]), причем робот может перейти из комнаты с номером X в комнату с номером Y только при условии X≤Y. Ваша задача подсчитать общее количество различных путей, которыми робот может добраться из комнаты [1;1] в комнату [N;N]. Два пути считаются различными, если они отличаются хотя бы одной комнатой.

Входные данные.

   N – размер лабиринта (2 ≤ N ≤ 10).

   A[1,1] A[1,2] … A[1,N]

   A[2,1] A[2,2] … A[2,N]

   …

   A[N,1] A[N,2] … A[N,N]

   A[I,J] – номер комнаты (0 ≤ A[I,J] ≤ 1000).

Выходные данные.

   Ответ на задачу - общее количество различных путей, которыми робот может добраться из комнаты [1;1] в комнату [N;N].

Пример.