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

[Anonymous]

Я пытаюсь решить эту проблему с помощью динамического программирования на C++.
По сути, это подсчет путей на карте (n x m) из ячейки, отмеченной буквой «D» ( расположенная в строке 0) в ячейку, отмеченную буквой «P» (расположенную в строке n-1).
Тем не менее, существуют некоторые ограничения и препятствия.

• Вы можете перемещаться только вправо, влево и вниз, и вы можете посетить ячейку только один раз в каждом отдельном пути.
  
  У меня есть боковые направляющие L, но мне не обязательно тратить их все. Перемещение более одного раза по горизонтали в одной и той же строке не считается слайдом.

Например, вот путь ( x) с тремя слайдами, двумя правыми и одним левым:

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

. D x x x .
. . . . x .
x x x x x .
x . . . . .
x x P . . .

• Там будут препятствия «О», от которых нам нужно отойти на осторожное расстояние в 3 клетки как по горизонтали, так и по вертикали.

Вот пример того, что означают «3 ячейки» (*):

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

. D . . . .
* * * * * .
* * * * * .
* * O * * .
* * * * * .
* * * * * .
. . . . . P

В этом примере существует только один возможный путь от D к P, для которого требуется 1 сдвиг вправо.

Я знаю, что эту проблему можно решить с помощью BFS, но я должен строго решить ее с помощью динамического программирования.
Итак, вот что я пробовал, но не смог сделать правильно:

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

#include
#include

using namespace std;

using VI = vector;
using VVI = vector;

using VP = vector
>;

using VVC = vector;

int n, m; // dim of the grid
int L; // number of lateral slides
VVI paths; // counting paths
VVC map; // initial grid

int f(int i, int j, int lat, int is_lateral){ // is-lateral indicates if i'm sliding laterally (1) or i switch to a down movement (0)
if(i < 0 or j < 0 or i >= n or j >= m) return 0; // outside of the map

char& cell = map[i][j] ;
int& pos = paths[i][j] ;

if(pos != -1 ) return pos; // already calculated

if(cell == 'O' or cell == 'x') return pos = 0; // it's a prohibited cell or already passed through it

if(lat < 0) return pos = 0; // overused number of slides, not valid position

if(cell == 'D') return pos = 1; // base case
cell = 'x'; // mark visited cell

// if we continue sliding horizontally, we don't spend slides thus lat remains the same
// if we switch to a down movement, we stop the sliding thus spending a lateral slide
int c = f(i-1, j, lat - is_lateral, 0) + f(i, j+1, lat, 1) + f(i, j-1, lat, 1);

cell = '.'; // unmark visited cell
return pos = c;
}

int main() {
while(cin >> n >> m){
cin >> L;
int b;
VP v; // vector for saving obstacles
map = VVC(n, vector(m));
paths = VVI(n, VI(m, -1)); // matrix for the recursion, counts how many paths there are from D (the doctor) to map[i][j]
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
char c;
cin >> c;
map[i][j] = c;
if(c == 'P') b = j; // P (the Plane) is in row n-1 and column b
if(c == 'O') {
pair P(i,j); // save obstacle to mark safe distance later
v.push_back(P);
}
}
}
// mark the safety distance
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) map[x][y] = 'O';
}
}
}
// print number of possible paths
cout 

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