Есть задачка:
Дана матрица a(m, n). Найдите в ней путь с максимальной суммой от какого-нибудь элемента первой строки до какого-нибудь элемента последней строки. Ходить можно вниз по вертикали или диагоналям.
Задачу нужно решить на С++ с помощью рекурсии, не используя STL и др. наворотов.
Проблема: есть рекурсивная функция, она работает, правильно ищет максимальную сумму, а вот с запоминанием пути выходит проблема. Запись в массивы идет неправильно... Помогите пожалуйста!
Код полностью:
Дана матрица a(m, n). Найдите в ней путь с максимальной суммой от какого-нибудь элемента первой строки до какого-нибудь элемента последней строки. Ходить можно вниз по вертикали или диагоналям.
Задачу нужно решить на С++ с помощью рекурсии, не используя STL и др. наворотов.
Проблема: есть рекурсивная функция, она работает, правильно ищет максимальную сумму, а вот с запоминанием пути выходит проблема. Запись в массивы идет неправильно... Помогите пожалуйста!
Код полностью:
Код:
#include <iostream>
#include <conio.h>
#include <math.h>
#include <vector>
#include <time.h>
using namespace std;
//Задаем глобальную матрицу статической размерности.
const int n=5;
const int m=6;
int matrix[n][m];
//В структуры подобного вида будет записан путь.
struct element
{
int row;
int col;
};
//Указатели на массив, содержащий путь.
element *massiv2;
element *massivtemp;
void Entermatr(int, int); //Функция для ручного ввода матрицы.
void Getmatr (int, int); //Функция, задающая матрицу из случайных чисел
void Myprint (int, int); //Функция, которая выводит матрицу
void Recfind(bool**, int&, int, int, int, element*, element*); //Рекурсивная функция поиска пути.
int main()
{
//Выбор пользователя.
int choice;
cout<<"Sposob zadaniya matricy:"<<endl;
cout<<"(1) -- vvod s klaviatury\n(2) -- matrica iz sluchainyh chisel\n";
cin>>choice;
switch (choice)
{
case 1:
{
cout<<"Razmernosti: "<<n<<" strok i "<<m<<" stolbcov.";
Entermatr (n,m);
break;
}
case 2:
Getmatr(n,m); break;
default:
cout<<"Wrong choice.";
}
//Обнуляем и инициализируем все вспомогательные переменные и указатели.
int sum=0;
massiv2=new element[n];
massivtemp=new element[n];
for (int i=0; i<n; i++)
{
massivtemp[i].col=0;
massivtemp[i].row=0;
}
for (int i=0; i<n; i++)
{
massiv2[i].col=0;
massiv2[i].row=0;
}
bool **field; //двумерное "поле"
field =new bool*[n];
for (int i=0; i<n; i++)
{
field[i]=new bool[m];
for (int j=0; j<m; j++) field[i][j]=false; // Первоначально никакую клетку не посетили
}
for (int i=0; i<m; i++) // Проходим по элементам первой строки
{
int temp_sum=0;
//cout<<"\nJ:"<<i<<endl;
Recfind(field,temp_sum,0,i,0, massiv2, massivtemp);
//cout<<"\nSum:"<<sum;
if (temp_sum>sum)
{
sum=temp_sum;
}
}
cout<<"Max: "<<sum<<endl;
//Вывод результата от рекурсии.
cout<<"Here is the path according to the recursive algorithm:\n";
for (int i=0; i<n; i++)
cout<<massiv2[i].row<<","<<massiv2[i].col<<endl;
Myprint(n,m);
delete []massiv2;
for (int i=0; i<n; i++)
delete []field[i];
delete []field;
_getch();
return 0;
}
void Entermatr(int n, int m)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
cin>>matrix[i][j];
}
}
void Getmatr (int n, int m)
{
int RANGE_MIN=0;
int RANGE_MAX=10;
srand((unsigned)time(NULL));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
matrix[i][j]=
static_cast<int>(((double)rand()/(double) RAND_MAX) * RANGE_MAX + RANGE_MIN);
}
}
void Myprint (int n, int m)
{
for(int i=0;i<n;i++)
{
cout<<endl;
for(int j=0;j<m;j++)
cout<<matrix[i][j]<<" ";
}
cout<<endl;
}
void Recfind(bool **field, int& sum, int i, int j, int s, element *massiv2, element *massivtemp)
{
//Условия выхода из рекурсии.
if (i<0 || i>=n || j<0 || j>=m)
return;
if (i==n-1)
{
if (s+matrix[i][j]>sum)
{
sum=s+matrix[i][j];
for (int i=0; i<n; i++)
{
massiv2[i].col=massivtemp[i].col;
massiv2[i].row=massivtemp[i].row;
}
}
return;
}
if (!field[i][j])
{
int temp_sum=0;
field[i][j]=true;
massivtemp[n-i-1].row=i;
massivtemp[n-i-1].col=j;
int temp=s+matrix[i][j];
Recfind(field,sum,i+1,j,temp, massiv2,massivtemp);
Recfind(field,sum,i+1,j-1,temp, massiv2, massivtemp);
Recfind(field,sum,i+1,j+1,temp, massiv2, massivtemp);
for (int i=0; i<n; i++)
{
massivtemp[i].col=0;
massivtemp[i].row=0;
}
field[i][j]=false;
}
}