Страницы

Поиск по вопросам

пятница, 12 июля 2019 г.

Изменение размера map

Мяч находится на игровом поле m на n в ячейке (i, j), его можно передвигать Найдите количество возможных путей вывода мяча за пределы игрового поля из исходного состояния не более чем за k шагов. Нет ограничения на посещение одной и той же точки несколько раз. То есть при большом k одна и та же клетка может быть пройдена несколько раз.
Необходимо написать алгоритм поиска количества путей из заданной позиции за пределы поля. Используя map в двумерном массиве сохраняю количество путей из конкретной позиции при конкретном количестве оставшихся доступных шагов. Но при рекурсивном вызове функции размер map без причины увеличивается до максимального. Не могу понять из-за чего такое происходит ибо на плюсах программировал не много.
#include #include #include #include #include #include struct MyStruct { std::map ok; }; int ik, jk, nk, mk, kk; int rec(int m, int n, int k,int i, int j,int result, MyStruct *arr ) { auto itMap = arr->ok.begin(); if (i<0 || j<0 || i==m || j==n) { result += 1; return result; } if (k==0) { return 0; } k = k - 1; if (arr[(i+1)*mk+j].ok.count(k)==0) { result += rec(m, n, k, i + 1, j, 0, arr); arr[(i + 1)*mk + j].ok.insert(std::pair(k, result)); } else { for (itMap= arr[(i + 1)*mk + j].ok.begin(); itMap != arr[(i + 1)*mk + j].ok.end(); itMap++) { if (itMap->first == k) { result += itMap->second; break; } } } if (arr[(i)*mk + j+1].ok.count(k) == 0) { result += rec(m, n, k, i, j + 1, 0, arr); arr[(i)*mk + j+1].ok.insert(std::pair(k, result)); } else { for (itMap = arr[(i)*mk + j+1].ok.begin(); itMap != arr[(i )*mk + j+1].ok.end(); itMap++) { if (itMap->first == k) { result += itMap->second; break; } } } if (arr[(i - 1)*mk + j].ok.count(k) == 0) { result += rec(m, n, k, i - 1, j, 0, arr); arr[(i - 1)*mk + j].ok.insert(std::pair(k, result)); } else { for (itMap = arr[(i - 1)*mk + j].ok.begin(); itMap != arr[(i - 1)*mk + j].ok.end(); itMap++) { if (itMap->first == k) { result += itMap->second; break; } } } if (arr[(i)*mk + j - 1].ok.count(k) == 0) { result += rec(m, n, k, i, j - 1, 0, arr); arr[(i)*mk + j - 1].ok.insert(std::pair(k, result)); } else { for (itMap = arr[(i)*mk + j - 1].ok.begin(); itMap != arr[(i)*mk + j - 1].ok.end(); itMap++) { if (itMap->first == k) { result += itMap->second; break; } } } return result; } void main() { std::cout.precision(10); int result; double start_time, end_time; std::ifstream fin("input.txt"); while (!fin.eof()) { start_time = omp_get_wtime(); fin >> mk>>nk>>kk>>ik>>jk; MyStruct *arr=new MyStruct[nk*mk]; result = 0; result=rec(mk,nk,kk, ik, jk,0,arr); end_time = omp_get_wtime(); std::cout << "m=" << mk << " n=" << nk << " k=" << kk << " i=" << ik; std::cout << " j=" << jk << " result=" << result << " time=" << end_time - start_time << std::endl; for (int count = 0; count < mk; count++) delete[]arr; } fin.close(); std::system("pause"); }


Ответ

В общем, рекурсивное решение здесь нельзя использовать. Рост числа элементов экспоненциальный (несколько доказать ну или проверить). Эта задача решается с помощью динамического программирования.
Формула
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 в конце можно не вызывать, оставил чтобы меньше вопросов было. Он ни на что не влияет (но это не сразу очевидно).

Комментариев нет:

Отправить комментарий