Форум программистов, компьютерный форум, киберфорум
Наши страницы

Задача нахождения кратчайшего пути - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Собеседования по С++ для джуна http://www.cyberforum.ru/cpp-beginners/thread1506665.html
Добрый день, если вы бы проводили собеседования по С++ для джуна - какой вопрос по С++ вы бы припасли как самый сложный? Для меня пока, что самый сложный вопрос (который расскрыл бы многие...
C++ Необязательные временные объекты Помогите с задачкой: Класс Car содержит модель автомобиля. Функция Find определяет, присутствует ли указанная модель в списке автомобилей. class Car { string model_; public: Car(string mod)... http://www.cyberforum.ru/cpp-beginners/thread1506633.html
C++ Уведомления между потоками
Здравствуйте! Набросал код для экспериментов: #include "stdafx.h" int блок_1(HWND *hWnd, MyStruct* strukt_1); int сервис_1(HWND *hWnd, MyStruct* strukt_1); void блок(HWND *hWnd, MyStruct*...
C++ Когда в ОС используется COM ?
Для каких действий ОС использует COM технологию ? Всегда ли она используется при исполнении exe файлов?
C++ Где найти все глаголы для ShellExecute ? http://www.cyberforum.ru/cpp-beginners/thread1506564.html
Здравствуйте. Где и как посмотреть список допустимых глаголов системы? Знаю о существовании страницы в msdn , но функция которую я нашел в интернете и использую использует глагол "runas",...
C++ Write some short C or C++ code to generate a segmentation fault Write some short C or C++ code to generate a segmentation fault подробнее

Показать сообщение отдельно
Simix
0 / 0 / 0
Регистрация: 13.04.2015
Сообщений: 3

Задача нахождения кратчайшего пути - C++

29.07.2015, 13:57. Просмотров 522. Ответов 3
Метки (Все метки)

Никак не могу понять почему в таких типах задач у меня ошибка. Помогите найти ошибку, и если сможете объясните её.
Условие
Робот-кладоискатель перемещается по квадратному клетчатому полю, размером 6 на 6 клеток.
Часть клеток поля содержит клады монет. Числа в клетках указывают, что в соответствующей клетке есть клад из этого количества монет.
0 10 0 1 0 B
3 0 4 0 1 0
7 0 0 4 0 0
0 0 3 0 0 5
0 6 0 2 0 0
A 0 3 0 9 6
Робот ищет клады, руководствуясь следующими правилами:
1. За один ход робот может перемещаться на одну клетку вправо, влево, вверх или вниз, не выходя за пределы поля.
2. На каждый ход робот тратит одну единицу энергии.
3. Если робот попадает в клетку с кладом, он забирает указанное в ней количество монет.
4. Батарейка робота содержит ровно 16 единиц энергии.
5. Перед началом движения робот находится в клетке «A». В ней нет клада.
6. Если робот попадает в клетку «B», он завершает движение, даже если у него осталась энергия. В клетке «B» нет клада.
7. Миссия робота считается успешной, только если он попал в клетку «B».
Определите, какое максимальное количество монет может быть у робота в результате успешного завершения миссии. В ответе укажите целое число.
Ответ: 36

Решение:

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <fstream>
 
using namespace std;
 
bool IsAvailable(int x,int y,int size)
{
    if((x >= 0) && (x < size) && (y >= 0) && (y < size))
        return true;
 
    return false;
}
 
int FindPath(int *matrix, int size, int x,int y,int sum,int Xod,int b1)
{
 
    static int minSum = -1; //минимальная сумма путей
    //если текущие координаты совпадают с концом пути,то
    //пересчитываем минимальную сумму
    Xod--;
    if(((x == 0) && (y == b1)))
    {
        if((sum > minSum)) //если текущая сумма меньше минимальной,то запоминаем ее
            minSum = sum;
    }
    else{
 
    if((IsAvailable(x+1,y,size))&&(Xod>0))
    {
        matrix+=(x+1)*6+y;
        FindPath(matrix,size,x+1,y,sum + *matrix, Xod, b1);
        matrix-=(x+1)*6+y;
    }
    if((IsAvailable(x,y+1,size))&&(Xod>0))
    {
        matrix+=x*6+y+1;
        FindPath(matrix,size,x,y+1,sum + *matrix, Xod, b1);
        matrix-=x*6+y+1;
    }
    if((IsAvailable(x-1,y,size))&&(Xod>0))
    {
        matrix+=(x-1)*6+y;
        FindPath(matrix,size,x-1,y,sum + *matrix, Xod, b1);
        matrix-=(x-1)*6+y;
    }
    if((IsAvailable(x,y-1,size))&&(Xod>0))
    {
        matrix+=x*6+y-1;
        FindPath(matrix,size,x,y-1,sum + *matrix, Xod, b1);
        matrix-=x*6+y-1;
    }
    }
    return minSum;
}
int main()
{
    int k=0, Xod2=0, A=-2, A1=0, B=-1, B1=0;
    int *arr;
    ifstream f("D:/Programmirovanie/C++/Iyul2015/Other/GameGoldd.txt");
    f>>k;
    const int x = k;
    f>>k;
    const int y = k;
    f>>Xod2;
    int Mas[x][y];
    k=0;
    for(int i=0; i<x; i++)
    {
        for(int j=0; j<y; j++)
        {
            k++;
            f>>Mas[i][j];
            cout<<Mas[i][j];
            if(Mas[i][j]==A)
                A1=k;
            if(Mas[i][j]==B)
                B1=k;
        }
    }
    cout<<A1;
    arr=&Mas[0][0];
    for(int i=0; i<x; i++)
    {
        for(int j=0; j<y; j++)
    {
        cout<<*arr<<" ";
        arr++;
    }
    cout<<endl;
    }
 
 
    cout<<FindPath(arr, 6, 5, 0, 0, 16, 5);
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.