Количество путей в лабиринте
(Время: 1 сек. Память: 16 Мб Сложность: 38%)
Для решения данной задачи применим принцип динамического программирования. Предположим, что для каждой клетки с некоторыми координатами (i,j) нам уже известно количество путей длиной в m шагов. Обозначим это значение как a[m][i][j]. Тогда завершающий шаг любого пути длиной m+1 в клетку (i,j) обязательно будет следовать из соседних клеток (i,j-1), (i,j+1), (i-1,j) и (i+1,j). Поэтому верно рекуррентное соотношение:
a[m+1][i][j]=a[m][i][j-1]+a[m][i][j+1]+a[m][i-1][j]+a[i+1][j]
Заметим, что все значения a[0][i][j] нам известны (они равны нулю, кроме a[0][1][1]=1), поэтому увеличивая m мы сможем вычислить количество путей для k шагов для каждой клетки. Ответом на задачу будет значение a[k][n][n]. Данный алгоритм можно представить следующим образом:
int a[31][16][16]
string c[1..15]
readln(n, k)
for i=1..n readln(c[i])
a[0][1][1]=1
for m=1..k
for i=1..n
for j=1..n
if(c[i][j]='0')
a[m][i][j]=a[m-1][i][j-1]+a[m-1][i-1][j]+a[m-1][i][j+1]+a[m-1][i+1][j]
write(a[k][n][n])
Заметим, что на каждом шаге нам достаточно знать значения, вычисленные на предыдущем, поэтому в целях экономии памяти можно ограничиться массивом меньшей размерности (использовать только 2 значения первой координаты).
| 
