Форум программистов, компьютерный форум CyberForum.ru

[C++] Задача "Пират в подземелье" - C++

Восстановить пароль Регистрация
 
Алексей Студент
0 / 0 / 0
Регистрация: 12.12.2008
Сообщений: 23
07.12.2011, 10:49     [C++] Задача "Пират в подземелье" #1
Всем доброго времени суток.
Прощу помощи в следующем.
Необходимо реализовать довольно широко известную задачу на С++:
Подземелье сокровищ.
В поисках драгоценных камней пират попадает в подземелье. Подземелье - прямоугольник, разделенный на NхM одинаковых по размеру комнат, в каждой из которых 4 двери, соединяющих их друг с другом. В каждой комнате стоят сундуки с золотыми монетами. Сундуки устроены так, что за одно посещение комнаты можно взять только определенное, заранее известное число монет. Для каждой комнаты это число разное. Дверь в любую другую соседнюю комнату можно открывать не раньше чем через 1 минуту. Каждую комнату можно посещать неограниченное число раз, правда, через каждые К минут все двери открываются и по комнатам проходит стража. Однако, в каждой комнате есть люк внизу, через который можно спокойно спуститься и покинуть сокровищницу. Надо составить план для пирата, позволяющий ему взять как можно больше монет за отведенные К минут.

Входные данные.
Заданы числа N,M и K.
Звдвна матрица NхM. Каждый элемент матрицы представляет количество монет, которые можно взять в соответствующей комнате за одно посещение.
Задано начало маршрута: левая верхняя комната (в ней стража забыла закрыть вентиляционный верхний люк).

Выходные данные должны быть представлены единственным числом, равным максимальному количеству монет, которые можно взять.

Пример исходных данных:
N=3, M=4 и K=7
Матрица:
1 1 1 1
1 1 2 1
1 1 2 3

Выходные данные для данного примера должны быть: 12.
В самом деле, чтобы собрать максимум, пирату надо пробраться к самой дальней от него комнате. При этом надо посетить комнаты третьего столбца. На это уйдет 6 минут. И последняя минута может быть использована для повторного посещения комнаты (3,3).
Итого: 1+1+1+2+2+3+2=12.
Нашел реализацию на Паскале, решил использовать тот же алгоритм - перебор с возвратом, используя рекурсивную функцию:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
using namespace std; 
int n, m, k;
int ** matrix;
int i=0; int sum=0; int sum1=0;
int dx[4]={1, 0, -1, 0};
int dy[4]={0, 1, 0, -1};
void solve(int x, int y, int p);
 
int main ()
{cout<<"Vvedite razmernost cherez probel"<<endl;
    cin>>n>>m;
    matrix = new int*[n];   
    for (int i=0; i<n; i++)
        matrix[i]=new int[m];
    cout<<"Fill matrix:"<<endl; 
    for (int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            cin>>matrix[i][j];
        }
    }
    cout<<"Your matrix: "<<endl;
    for (int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            cout<<matrix[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<"Kolichestvo hodov: "<<endl;
    cin>>k;
    
    solve(0,0,k);
    cout<<"Kolichestvo kamnei: "<<sum1<<endl;
    
return 0;
}
 
void solve(int x, int y, int p)
    {if (p==0) 
        {if (sum>sum1) sum1=sum;}
     else
         {for (i=0;i<4; i++)
              {if (((x+dx[i])<m)&&((x+dx[i])>=0)&&((y+dy[i])<n)&&((y+dy[i])>=0))
                  {sum = sum + matrix[x+dx[i]][y+dy[i]];
                  solve(x+dx[i], y+dy[i], p-1);
                  sum = sum - matrix[x+dx[i]][y+dy[i]];
                  }
              }
         }    
     }
Код компилится, однако при выполнении, после ввода исходных данных, практически мгновенно вываливается с ошибкой. Предполагаю, что неточности есть в условии возможности перехода в следующую клетку, но разобраться не могу, мозг закипает (ну несколько далек я, как дизайнер-верстальщик, от программирования подобных задач на Си), а на допуск сделать нужно.

Прощу помощи в поиске ошибки и ее исправлении, заранее благодарен.

Добавлено через 58 минут
Апдейт:
Поковырялся еще немного, чуть изменил порядок действий в рекурсивной функции:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
using namespace std;
 
int sum=0;
int x=0, y=0;               
int N, M, k;                
int rez=0;
int dX[4]={1, 0, -1, 0};
int dY[4]={0, 1, 0, -1};
int k_copy=0;
int** matrix;
 
void solve(int x, int y, int k_copy);
 
 
int main()
{   setlocale(0, "Russian");
    cout<<"Введите количество ходов: ";
    cin>>k;
    cout<<"Введите размерность матрицы (пример: 4 4)"<<endl;
    cin>>N>>M;
    matrix = new int*[N];   
    for (int i=0; i<N; i++)
        matrix[i]=new int[M];   
    cout<<"Fill matrix:"<<endl; 
    for (int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            cin>>matrix[i][j];
        }
    }
    cout<<"Введенная матрица: "<<endl;
    for (int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            cout<<matrix[i][j]<<" ";
        }
        cout<<endl;
    }
    k_copy=1;
    solve(0, 0, k_copy);    
    cout<<"Summa is: "<<rez<<endl;
    return 0;
}
 
 
 
 
 
 
void solve(int x, int y, int k_copy)
{
    sum = sum + matrix[x][y];
    if(k_copy==k)
    {
        if(sum>rez) rez=sum;
        return;
    }
    else
    {
        for(int i=0; i<4; i++)
        {
            if ((x+dX[i])>=0&&(x+dX[i])<N&&(y+dY[i])>=0&&(y+dY[i])<M)
            {
                solve(x+dX[i], y+dY[i], k_copy+1);
                sum = sum - matrix[x+dX[i]][y+dY[i]];
                
            }
            else
                continue;
        
        }
    }
}
И вроде бы работает правильно, по крайней мере придумал еще 2 примера матриц, и результаты совпали с тем, что я насчитал сам.
Тем не менее, если кто-нибудь заметит какие-либо неточности, способные привести к неправильным подсчетам, буду только признателен.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.12.2011, 10:49     [C++] Задача "Пират в подземелье"
Посмотрите здесь:

Строка: заменить первую "о" на "а", удалив остальные "о" C++
C++ Определить, сколько в строке символов "*", ":", ";"
Все слова, не содержащие "bc" и заканчивающиеся на "ad" заменить на "!" C++
C++ Подскажите как перегрузить операторы ">>", "<<" и "="
Задача "Кто старше?" (подскажите где ошибка в коде) C++
C++ Необработанное исключение в "0x104b2288" в "Matrix.exe": 0xC0000005: Нарушение прав доступа при записи "0xcdcd
C++ Переменные "емкость", "Галлон", "Бензин"
Классы "Фигура", "Прямоугольник", "Круг" C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 17:46. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru