Мяч находится на игровом поле m на n в ячейке (i, j), его
можно передвигать Найдите количество возможных путей вывода мяча за
пределы игрового поля из исходного состояния не более чем за k шагов.
Нет ограничения на посещение одной и той же точки несколько раз. То
есть при большом k одна и та же клетка может быть пройдена несколько
раз.
Необходимо написать алгоритм поиска количества путей из заданной позиции за пределы поля. Используя map в двумерном массиве сохраняю количество путей из конкретной позиции при конкретном количестве оставшихся доступных шагов. Но при рекурсивном вызове функции размер map без причины увеличивается до максимального. Не могу понять из-за чего такое происходит ибо на плюсах программировал не много.
#include
Ответ
В общем, рекурсивное решение здесь нельзя использовать. Рост числа элементов экспоненциальный (несколько доказать ну или проверить). Эта задача решается с помощью динамического программирования.
Формула
F[s][i][j] := число способов пройти от стартовой точки к {i,j} за s шагов.
{i,j} \in [0,N)*[0,M) s \in [0,K]
База
F[0][ i][ j] = 0
F[0][x0][y0] = 1
Пересчёт
F[s+1][i][j] = F[s][i-1][j-1] + F[s][i-1][j+1] + F[s][i+1][j-1] + F[s][i+1][j+1]
если элемента нету, то считаем равным 0.
Ответ - накопительные выходы за границы.
Примерный код на слоях (чисто для понимания, не факт что компилируется). Константы размера потом подберёте, например 10000.
/**
@params N,M - размер
@params x0,y0 - начальная точка
@params K - число шагов
@output - ответ
*/
long long DP[2][maxN][maxM]; //fill 0
#define get(s,i,j) ((i < N && j < M && i>=0 && j>= 0)? DP[s][i][j]:0)
long long calc(int N, int M, int x0, int y0, int K){
long long ans = 0;
DP[0][x0][y0] = 1;
for (int k=1;k <= K; k++){
int pr = k&1;
int r = 1 - pr;
for (int i=0;i < N; i++) //границы к ответу
ans += DP[r][i][0] + DP[r][i][M-1];
for (int j=0;i < M; j++) //границы к ответу
ans += DP[r][0][j] + DP[r][N-1][j];
for (int i=0; i < N; i++)
for (int j=0; j < M; j++)
DP[pr][i][j] = get(r,i-1,j-1) + get(r,i-1,j+1)
+ get(r,i+1,j-1) + get(r,i+1,j+1);
memset(DP[r], 0 ,sizeof(DP[r]));
}
return ans;
}
Сложность O(nmk) по времени O(nm) по памяти.
В теории задача может быть сжата до формул (весьма громоздких), но это уже выходит за рамки вопроса.
P.S. memset в конце можно не вызывать, оставил чтобы меньше вопросов было. Он ни на что не влияет (но это не сразу очевидно).
Комментариев нет:
Отправить комментарий