Подсчет количества путей с помощью динамического программирования ⇐ C++

[Anonymous]

У меня есть такое утверждение из задачи, которую я пытаюсь решить в рамках курса, но не могу решить правильно:
Профессор Уильям Дайер из знаменитого Университета Мискатоник находится в большая опасность. Он обнаружил и начал исследовать колоссальный затерянный город на плато Ленг в Антарктике только для того, чтобы понять, что он не одинок: ужасные существа, колонизировавшие Землю два миллиарда лет назад, все еще здесь! Теперь профессор Дайер спасается бегством, спускаясь с ледяного холма, пытаясь добраться до своего самолета у подножия холма, а его преследует шоггот. Профессор Дайер может бежать вниз, но не вверх, возможно, с некоторыми движениями влево или вправо. У него как раз хватает энергии, чтобы заставить L такие боковые движения скользить по льду.
Что еще хуже, во льду под ногами профессор Дайер может видеть других спящих существ, Древних. , который он мудро желает не будить. Поэтому он решает рассматривать холм как прямоугольную сетку, чтобы оставлять осторожное расстояние в 3 клетки, как по горизонтали, так и по вертикали, между ним и каждым Стариком на протяжении всего пути от его исходной позиции до плоскости.
Буква «D» указывает на позицию профессора Дайера. Буква «P» указывает положение самолета. Обратите внимание: профессор Дайер никогда не будет тратить энергию, перемещаясь по горизонтали более одного раза в одном и том же ряду.
Ввод
Ввод состоит из нескольких случаев. Каждый случай начинается с 2 < R < 15 и 1 < C < 15, количества строк и количества столбцов сетки соответственно, за которым следует максимальное количество боковых движений 0 < L < R. Затем следуют R строк с Каждый символ C: '.' обозначает пустую позицию; буква «О» означает «Старый». В первой строке ровно одна буква «D», а в последней — одна буква «P». Специальный тестовый пример с R = C = L = 0 отмечает конец ввода.
Вывод
Проф. Дайер почувствовал бы облегчение, если бы вы указали ему путь к отступлению. Но давайте будем жестокими. Для каждого тестового примера просто сообщайте ему количество различных путей выхода.
Я знаю, что эту задачу можно решить с помощью BFS, но я должен строго решить ее с помощью динамического программирования (в этом случае мы используем C++). конечно).

Вот несколько примеров входов и соответствующих им выходов:
Вход

Код: Выделить всё

12 11 2
....D......
...........
...........
...O.....O.
...........
...........
...........
...........
...........
..OO.......
...........
......P....

5 5 5
....D
.....
.....
.....
P....

4 4 4
.D.O
....
....
...P

Вывод[/b]

Код: Выделить всё

2
625
0

И вот что я пробовал, но не получилось:

Код: Выделить всё

#include
#include

using namespace std;

using VI = vector;
using VVI = vector;

using VP = vector
>;

using VVC = vector;

int n, m; // n rows m columns
int L; // number of lateral movements
VP v; // vector for obstacles
VVI C; // counting paths
VVC M; // initial grid

int f(int i, int j, int lat, int lateral){
if(i < 0 or j < 0 or i >= n or j >= m) return 0;

char& cas = M[i][j] ;
int& pos = C[i][j] ;

if(pos != -1 ) return pos;

if(cas == 'O' or cas == 'x') return pos = 0;

if(lat < 0) return pos = 0;

if(cas == 'D') return pos = 1;
cas = 'x';
int c = f(i-1, j, lat-lateral, 0) + f(i, j+1, lat, 1) + f(i, j-1, lat, 1);
cas = '.';
return pos = c;
}

int main() {
while(cin >> n >> m){
cin >> L;
int b;
v.clear();
M = VVC(n, vector(m));
C = VVI(n, VI(m, -1));
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
char c;
cin >> c;
M[i][j] = c;
if(c == 'P') b = j;
if(c == 'O') {
pair P(i,j);
v.push_back(P);
}
}
}
for(pair p : v){
int i = p.first;
int j = p.second;
for(int x = i-2; x = 0 and x < n and y < m) M[x][y] = 'O';
}
}
}
cout 

Подробнее здесь: [url]https://stackoverflow.com/questions/78649690/counting-the-number-of-paths-with-dynamic-programming[/url]