VPF::[С++] Поиск пути по клеткам с максимальной суммой

tymrfik

Дата 21.1.2011, 10:28 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 10
Регистрация: 20.1.2011

Репутация: нет
Всего: нет

За долгую и верную службу Рыцарю позволено набрать сокровищ в сокровищнице своего сеньора. Сокровищница имеет форму прямоугольника, состоящего из отдельных "клеток" — прямоугольных комнат. В каждой комнате хранятся сокровища известной стоимости. Рыцарь может вынести сколько угодно сокровищ, но пройдя через сокровищницу только один раз. Он может начать с любой комнаты вдоль внешней северной стены сокровищницы (выбор комнаты — за рыцарем). На каждом шаге он может переходить в одну из трех "южно-соседних" комнат: южную, юго-восточную или юго-западную. Из комнат, граничащих с восточной или западной внешней стеной, возможны только два направления выхода. Закончить путь Рыцарь должен в любой из комнат на южной внешней стороне сокровищницы.
У Рыцаря есть план сокровищницы — прямоугольная таблица, в которой обозначены стоимости сокровищ каждой комнаты. Направлению с севера на юг соответствует направление сверху вниз на карте.
По заданной карте нужно найти один из допустимых путей, обеспечивающих наибольшую возможную сумму сокровищ.

Вход. Первая строка в тексте содержит два числа 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, а для это как я понимаю необходимо и двумерный массив задавать без случайных чисел (с этим справилась), а вот как тут сделать с МЕМОИЗАЦИЕЙ?!!!!!! Срочно пожалуйста помогите!

tymrfik

Дата 26.1.2011, 19:19 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 10
Регистрация: 20.1.2011

Репутация: нет
Всего: нет

Ладно, забудем про тот код, он мне пока не пригодился. ПОМОГИТЕ ПОЖАЛУЙСТА С САМОЙ РЕКУРСИЕЙ. Вот что я думаю о том как должна выглядеть просто рекурсия, вроде псевдокода:

Код

int rec(int i,int j){
if(i==n-1) return m[i][j];
if(j==0) {s1 и s3}
if(j==m-1) {s1 и s2}
s1=m[i][j]+rec(i+1,j-1);
s2=m[i][j]+rec(i+1,j);
s3=m[i][j]+rec(i+1,j+1);
return(max(s1,s2,s3));

Благодарна буду за идеи!!! Прошу!!! Подскажите как быть с самыми первыми ячейками [0][0], [0][1], .....[0][m-1]?!!!!! их нужно сначала перебирать через цикл и считать для них сумму?!!!! Помогите с кодом!!!! (До утра успеть бы. Зачет.)
ЕЩЕ Волнующие вопросы: как быть с первыми ячейками таблицы? и саму функцию нахождения максимума потом как подключить, т.е через класс?!

Это сообщение отредактировал(а) tymrfik - 26.1.2011, 19:20

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »