VPF::Поиск максимальной суммы по клеткам матрицы

tymrfik

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

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

Загрузка ...

Новичок

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

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

Цитата

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

Вход. Первая строка в тексте содержит два числа N и М, обозначающие "ширину" и "высоту", далее М строк по N неотрицательных целых чисел в каждой — стоимости сокровищ соответствующих комнат. Размеры сокровищницы не более чем 80x80 комнат.
Выход. В первой строке указывается номер (по порядку с запада на восток) комнаты северного ряда, из которой нужно начать движение, во второй — строка символов, означающих на¬правление очередного перехода (S — на юг, Е — на юго-восток, W — на юго-запад); в третьей — полученная максимально возможная суммарная стоимость. Если есть несколько путей с максимальной суммой, вывести любой из них.

Код


#include <cstdlib>
#include <iostream>
#include <fstream>
#include <stdio.h>
using namespace std;

int s[3]

int maxim()
 {
   int k;
   max=s[0];
   for(k=0;k<3;k++)
   {
      if(max<s[k]) 
        max=s[k];
           }
 }
int rec(int i, int j)
{
    if(i==n-1)return m[i][j];
    if(j==0) {};
    if(j==m-1){};
    s[0]=m[i][j]+rec(i+1,j-1);
    s[1]=m[i][j]+rec(i+1,j);
    s[2]=m[i][j]+rec(i+1,j+1);
    return(maxim(s[0],s[1],s[2]));
}
int main(int argc, char * argv[])
{
 int s[100];
 int n = 0;
 int m = 0;

 int **a;

 //îòêðûâàåì ôàéë
 FILE * fp = fopen("test.txt", "r");
 if (fp)
 {
  fscanf(fp, "%d %d", &n, &m);

  *a = new int(n);
  for (int i = 0; i < n; i++) a[i] = new int(m);

  for (int i = 0; i < n; i++)
  {
   for (int j = 0; j < m; j++)
   {
    fscanf(fp, "%d", &a[i][j]);
   }
  }
  
  fclose(fp);
 }

 for (int i = 0; i < n; i++)
 {
  for (int j = 0; j < m; j++)
  {
   printf("%d ", a[i][j]);
  }

  printf("\n");
 }

/* for (int i = 0; i < n; i++) delete a[i];
 delete *a;*/

system("PAUSE");
    return EXIT_SUCCESS;
}

Я только начала разрабатывать код (времени в обрез). Помогите пожалуйста!!! Как правильнее найти максимум. И еще один нюанс у меня возникает как обработать ячейки первой строки - чтобы с них начался путь. И вообще в целом мой код еще более похож на псевдокод - это насчет реализации рекурсии, помогите!!!!!SOS!!! smile

Срочно, завтра зачет...прошу!

xvr

Дата 27.1.2011, 13:09 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

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

Цитата

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

От наличия в задачи рекурсии (каковой у вас кстати нет) задача не решится волшебным образом smile

Составьте алгоритм решения, потом станет ясно куда там приделать рекурсию smile

В вашем случае рекурсию можно прицепить к полному перебору, что для размера 80х80 будет явный перебор (по времени smile

)

Код


int total_rows, total_cols;
int matrix[80][80];
int track[80];

int find_way(int start_row, int entry_col)
{
 if (start_row>=total_row) return 0;
 track[start_row]=entry_col;
 int max_val=0;
 int max_dir=0;

 for(int i=-1;i<2;++i)
  {
   if (entry_col+i<0 || entry_col+i>=total_cols) continue;
   int val=find_way(start_row+1,entry_col+i);
   if (val>=max_val) {max_val=val; max_dir=i;}
  }
 return matrix[start_row][entry_col]+find_way(start_row+1,entry_col+max_dir);
}

void try_all_entries()
{
 int max_val=0;
 int max_ent=0;
 for(int i=0;i<total_cols;++i)
  {
   int val=find_way(0,i);
   if (val>=max_val) {max_val=val; max_ent=i;}
  } 
 find_way(0,max_ent);
}

Заполнение массива (и количества колонок/столбцов), а так же печать результата (и перевод его из последовательности номеров колонок в направления) оставляю вам для самостоятельной работы

Это сообщение отредактировал(а) xvr - 27.1.2011, 13:11

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