Raghurss Ответов: 4

Где я ошибся в этом рекурсивном решении? Для этого существует итеративное решение dp, но я хочу знать свою ошибку здесь. Кто-нибудь, пожалуйста, дайте мне знать!

Дана золотая жила (M) n*m размеров. Каждое месторождение в этом руднике содержит положительное целое число, которое представляет собой количество золота в тоннах. Изначально майнер находится в первом столбце, но может быть и в любой строке. Он может двигаться только (вправо->,вправо вверх /,вправо вниз\), то есть из данной ячейки майнер может двигаться в ячейку по диагонали вверх вправо или вправо или по диагонали вниз вправо. Ваша задача состоит в том, чтобы узнать максимальное количество золота, которое он может собрать.

Вход : M[][] = {{1, 3, 3},
{2, 1, 4},
{0, 6, 4}};
Выход : 12
{(1,0)->(2,1)->(2,2)}

Вход: M[][] = {{1, 3, 1, 5},
{2, 2, 4, 1},
{5, 0, 2, 3},
{0, 6, 1, 2}};
Выход : 16
(2,0) -> (1,1) -> (1,2) -> (0,3) или
(2,0) -> (3,1) -> (2,2) -> (2,3)

Что я уже пробовал:

#include<iostream>
#include<vector>
using namespace std;
int func(vector<vector<int>>a,int p,int q,int n,int m,int ans)
{
    if(q==m-1)
    {
     return ans;
    }
    if(p==0)
    {
     return max(func(a,p,q+1,n,m,ans+a[p][q+1]),func(a,p+1,q+1,n,m,ans+a[p+1][q+1]));
    }
    else if(p==n-1)
    {
     return max(func(a,p,q+1,n,m,ans+a[p][q+1]),func(a,p-1,q+1,n,m,ans+a[p-1][q+1]));
    }
    else
    {
     return max(func(a,p,q+1,n,m,ans+a[p][q+1]),
       max(func(a,p-1,q+1,n,m,ans+a[p-1][q+1]),func(a,p+1,q+1,n,m,ans+a[p+1][q+1])));
    }
}
int main()
 {
	//code
	int t;
	cin>>t;
	while(t--)
	{
	    int n,m;
	    cin>>n>>m;
	    vector<vector<int>>a;
	    for(int i=0;i<n;i++)
	    {
	        for(int j=0;j<m;j++)
	        {
	            int temp;
	            cin>>temp;
	            a[i].push_back(temp);
	        }
	    }
	    int p=0;
	    int q=0;
	    int ans=0;
	    cout<<func(a,p,q,n,m,ans+a[0][0])<<endl;
	}
	return 0;
}

Gerry Schmitz

Никто не сможет расшифровать ваши бессмысленные имена переменных ... включая себя.

Raghurss

🤐😅

4 Ответов

Рейтинг:
9

KarstenK

Это зависит от вас, чтобы отладить код, но это поможет вам, когда вы используете лучшие имена и некоторые структурированные данные, такие как структуры для позиции. Это также поможет очистить структуру вашего кода. Наряду с этим вы должны сделать больше выходных данных, таких как "найдено X gold at (x,y)".

бонусный совет 1: Используйте некоторый кодированный массив шахт для отладки, поэтому вам не нужно вводить его.
бонусный совет 2: Используйте временные значения в коде "func"
бонусный совет 3: Используйте const и ссылку в вызове подпрограммы 

const vector<vector<int>> &a
чтобы избежать создания копий вектора в вызовах. Это улучшит скорость и облегчит отладку-

Raghurss

великая проницательность! Большое спасибо

Рейтинг:
35

CPallini

В качестве отправной точки попробуйте

#include <iostream>
#include <vector>
using namespace std;


using Matrix = vector< vector <int > >;

int maxsum( const Matrix & m, size_t r, size_t c)
{
  if ( c == m[r].size()-1)
    return m[r][c];

  int contrib = maxsum( m,r, c+1); //same row contribution

  if ( r == 0)
    contrib = max( contrib, maxsum( m, r+1, c+1));
  else if ( r == m.size()-1)
    contrib = max( contrib, maxsum(m, r-1, c+1));
  else
    contrib = max( contrib, max( maxsum(m, r+1, c+1), maxsum(m, r-1, c+1)));

  return (m[r][c] + contrib);
}

int main()
{
  size_t R,C; // R rows, C columns
  cin >> R >> C;

  vector < vector <int> > m(R);


  for (auto & v : m)
    for (size_t c = 0; c < C; ++c)
    {
      int i;
      cin >> i;
      v.push_back(i);
    }


  int maxgold = 0;
  for (size_t r = 0; r < R; ++r)
  {
    int gold = maxsum(m, r, 0);
    if  (maxgold < gold)
      maxgold = gold;
  }

  cout << "max gold = " << maxgold << endl;

}

Raghurss

Спасибо!! Я придумал это сейчас, используя мемуаризацию. Большое спасибо.

CPallini

Добро пожаловать.

Рейтинг:
1

OriginalGriff

Я не пробираюсь через этот беспорядок кода, чтобы попытаться понять, что, черт возьми, он должен делать, а тем более как он это делает - и отсутствие документации и использование бессмысленных односимвольных переменных является большим фактором в этом.

Так что все будет зависеть от тебя. Запустите его в отладчике (google расскажет вам, как им пользоваться) и внимательно следите, чтобы точно узнать, что происходит.

Но... если q начинается с m, а p равно нулю, он всегда будет взрывать стек ...

Raghurss

Приношу свои извинения за эту бессмысленную чепуху. Я очень торопился исправить свою ошибку! Да, я так и сделаю. Спасибо!

Рейтинг:
0

Stefan_Lang

Цитата:
a[i].push_back(temp);

Не знаю, как компилятор справится с этим, но std::vector всегда инициализируется как пустой, если не указано иное. Следовательно a[i] не определяется ни для какого значения i. Вам нужно изменить размер a прежде чем получить к нему доступ.

Raghurss

О! Спасибо за предложение.