Помогите найти ошибку. В каких-то случаях программа работает корректно, а в каких-то выдает ошибку. Закономерности я не вижу. Проблема с выводом ходов, если поле 1х1 понятна, но вроде поля 1х1 в задаче быть и не может. И правда, куда тогда идти?
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector < vector<int> > A(n+1, vector<int> (m+1));
for ( int i = 1; i < n+1; ++i){
for ( int j = 1; j < m+1; ++j){
cin >> A[i][j];
}
}
for ( int i = 1; i < n+1; ++i){
for ( int j = 1; j < m+1; ++j){
A[i][j] += max( A[i-1][j], A[i][j-1]);
}
}
cout << A[n][m] << endl;
vector<string> W;
while ( n != 1 || m != 1){
if ( A[n-1][m] > A[n][m-1]){
W.push_back("D");
--n;
}
else{
W.push_back("R");
--m;
}
}
for ( int i = W.size(); i >= 0; --i){
cout << W[i-1] << " ";
}
}
Для 1x1 стоимость без маршрута выводится.
В последнем цикле ошибка: i > 0 условие должно быть. Либо сделать int i = (int)W.size() - 1, и при распечатке единицу не надо отнимать.
#include <iostream>
#include <vector>
using namespace std;
typedef vector<vector<uint16_t>> vec;
struct obj
{
static obj best;
static vec map;
uint16_t value{};
string path{};
uint16_t x{}, y{};
obj move_right()
{
obj temp = *this;
temp.y += 1;
temp.path += 'R';
return temp;
}
obj move_down()
{
obj temp = *this;
temp.x+=1;
temp.path += 'D';
return temp;
}
};
vec obj::map = { {1,1,1} , { 0,0,2 }, { 0,1,3 } }; // для испытаний забинден
// для релиза здесь пустое обьявление, а задание размера и содержания сделать
// отдельно;
obj obj::best={};
uint16_t finder(obj it)
{
it.value += obj::map[it.x][it.y];
if (it.x == obj::map.size() - 1 && it.y == obj::map[0].size() - 1)
{
if (it.value > obj::best.value) obj::best = it;
return 1;
}
return (it.x < obj::map.size() - 1 ? finder(it.move_down()) : 0) + (it.y < obj::map[0].size() - 1 ? finder(it.move_right()) : 0);
}
int main()
{
obj start;
finder(start);
cout << obj::best.path << " " << obj::best.value;
}
Наверное поздновато, но изначально я допустил в програме небольшую оплошность и это стоило мне волос на голове. Пока искал в чем проблема - удалил часть с заполнением массива. но это не важно.
