У меня проблемы с алгоритмизацией, и у меня проблемы с управлением функциями, векторами и строками в C ++.
Мне нужно найти конкретный путь в матрице, и для этого мне нужно иметь все разные пути, поэтому я решил использовать функцию. Эта функция будет проверять, где продолжить поиск. Вот код функции:
vector<string> get_all_paths(string actual, int rows, int columns, int col_actual, int row_prev) {
vector<string> solutions;
int row_actual = (rows+row_prev-1)%rows;
for (int i = 0; i < 3; i++) {
cout << col_actual << " " << row_actual << "\n";
//cout << (dp[row_prev][col_actual+1] - matrix[row_prev][col_actual+1]) << " " << dp[row_actual][col_actual] << "\n";
if( (dp[row_prev][col_actual+1] - matrix[row_prev][col_actual+1]) == dp[row_actual][col_actual] ) {
if (col_actual > 0) {
//cout << "--" << actual << " " << row_actual << "\n";
string branch = actual + to_string(row_actual+1) + " ";
solutions = get_best_path(branch, rows, columns, col_actual-1, row_actual);
//cout << ".." << actual << "\n";
} else {
//cout << actual << " " << row_actual << "\n";
cout << actual << "\n";
string branch = actual.c_str();
branch += to_string(row_actual+1);
cout << branch << "\n";
solutions.push_back( branch );
break;
}
}
row_actual = (row_actual+1)%rows;
}
for(auto i : solutions) cout << "--" << i << "\n";
return solutions;
}
А вот и вызов метода:
vector<string> solutions;
for (int i = 0; i < rows; i++) {
if (dp[i][cols-1] == min_path) {
cout << "................\n";
solutions = get_best_path( (to_string(i+1)+" "), rows, cols, cols-2, i);
for(auto i : solutions) {
reverse(i.begin(), i.end());
cout << i << "\n";
}
cout << "xxxxxxxxxxxxxxx\n";
}
}
Дело в том, что я получаю три пути для данного примера, это правильно, но это все одна и та же строка, которая является последним путем или последним изменением, сделанным в переменной branch .
Может быть, я смешиваю много понятий и, возможно, это отвечали много раз, но я искал это и ничего не получил.
РЕДАКТИРОВАТЬ: я не получаю три пути от функции, только последний, но при печати внутри функции пути у меня есть три внутри этой функции, все с одинаковым значением, извините за это.
EDIT2: Идея проблемы состоит в том, чтобы найти путь минимальной стоимости в данной матрице и, если их больше 1, тот, который является самым маленьким лексикографически. Итак, с учетом матрицы:
5 4
9 1 9 9
1 9 9 9
9 9 9 9
1 1 1 1
9 9 1 9
Мой подход заключается в использовании dp в качестве матрицы с результатами программирования Dynami c, а затем я пытаюсь воссоздать все пути в функции выше.
В этом случае матрица dp:
9 2 11 12
1 10 11 20
9 10 11 12
1 2 3 4
9 10 3 12
Итак, лучшие пути:
4 4 4 4
4 5 4 4
2 1 5 4
И один правильный - последний.
Внутри моей функции я получаю разные пути и добавляю их в вектор результатов, но тогда я теряю их при поиске большего.
Спасибо за время, если вы прочитали это: D!