За долгую и верную службу Рыцарю позволено набрать сокровищ в сокровищнице своего сеньора. Сокровищница имеет форму прямоугольника, состоящего из отдельных "клеток" — прямоугольных комнат. В каждой комнате хранятся сокровища известной стоимости. Рыцарь может вынести сколько угодно сокровищ, но пройдя через сокровищницу только один раз. Он может начать с любой комнаты вдоль внешней северной стены сокровищницы (выбор комнаты — за рыцарем). На каждом шаге он может переходить в одну из трех "южно-соседних" комнат: южную, юго-восточную или юго-западную. Из комнат, граничащих с восточной или западной внешней стеной, возможны только два направления выхода. Закончить путь Рыцарь должен в любой из комнат на южной внешней стороне сокровищницы.
У Рыцаря есть план сокровищницы — прямоугольная таблица, в которой обозначены стоимости сокровищ каждой комнаты. Направлению с севера на юг соответствует направление сверху вниз на карте.
По заданной карте нужно найти один из допустимых путей, обеспечивающих наибольшую возможную сумму сокровищ.
Вход. Первая строка в тексте содержит два числа N и М, обозначающие "ширину" и "высоту", далее М строк по N неотрицательных целых чисел в каждой — стоимости сокровищ соответствующих комнат. Размеры сокровищницы не более чем 80x80 комнат.
Выход. В первой строке указывается номер (по порядку с запада на восток) комнаты северного ряда, из которой нужно начать движение, во второй — строка символов, означающих на¬правление очередного перехода (S — на юг, Е — на юго-восток, W — на юго-запад); в третьей — полученная максимально возможная суммарная стоимость. Если есть несколько путей с максимальной суммой, вывести любой из них.
| Код |
#include <iostream>
#include <math.h>
#include <vector>
using namespace std;
const int n=4;
const int m=5;
int matrix[n][m];
void Getmatr (int, int); //матрица из случайных чисел
void Myprint (int, int); //выводит матрицу
void find(bool**, int&, int, int, int);
int main()
{
int sum=0;
bool **field; //двумерное "поле"
field =new bool*[n];
for (int i=0; i<n; i++)
{
field[i]=new bool[m];
for (int j=0; j<n; j++) field[i][j]=false; // Первоначально никакую клетку не посетили
}
Getmatr(n,m);
for (int i=0; i<m; i++) // Проходим по элементам первой строки
{
int temp_sum=0;
find(field,temp_sum,0,i,0);
if (temp_sum>sum) sum=temp_sum;
}
Myprint(n,m);
cout<<"Max: "<<sum<<endl;
int a;
cin>>a;
for (int i=0; i<n; i++)
delete []field[i];
delete []field;
return 0;
}
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 find(bool **field, int& sum, int i, int j, int s)
{
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];
return;
}
if (!field[i][j])
{
field[i][j]=true;
int temp=s+matrix[i][j];
find(field,sum,i+1,j,temp);
find(field,sum,i+1,j-1,temp);
find(field,sum,i+1,j+1,temp);
field[i][j]=false;
}
|
}
Надо из этого сделать мемоизацию! Прошу помогите?!!!! Вроде нужно переписать функцию void find, а для это как я понимаю необходимо и двумерный массив задавать без случайных чисел (с этим справилась), а вот как тут сделать с МЕМОИЗАЦИЕЙ?!!!!!! Срочно пожалуйста помогите!  |