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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Simix
0 / 0 / 0
Регистрация: 13.04.2015
Сообщений: 3
#1

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

29.07.2015, 13:57. Просмотров 419. Ответов 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;
}
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.07.2015, 13:57     Задача нахождения кратчайшего пути
Посмотрите здесь:

Написать программу для нахождения кратчайшего пути между заданными вершинами графа - C++
visual studio windows forms нужна программа,которая будет вычислять кратчайший путь от вершины a до вершины b в графе, граф задается...

Задача (вывести длину кратчайшего пути от точки до точки.) - C++
Пишу задачу, нужно вывести длину кратчайшего пути от точки до точки. проблема в том, что после генерации массива и задания ему...

Нахождение кратчайшего пути - C++
Нужно сделать программу,чтоб она находила кратчайший путь от города 1 до города 2 на карте. Как реализовать в коде не знаю, помогите. ...

Восстановление кратчайшего пути в графе - C++
Есть алгоритм нахождения кратчайших путей(Флойд), а как восстановить путь как узнать через какие вершины он прошел?туплю прогаю с утра)) ...

Поиск кратчайшего пути (рекурсия) - C++
Помогите пожалуйста. Пусть имеется n городов. Некоторые из них соединены дорогами известной длины. С помощью рекурсии найти Кратчайшие...

Поиск кратчайшего пути на клетчатом поле. - C++
Дано клетчатое поле (допустим n x n). На некоторые клетки наступать нельзя. Дана начальная клетка, дана конечная клетка. Надо найти...

Определение кратчайшего пути алгоритмом Дейкстры - C++
Разработка программного комплекса для определения кратчайшего пути алгоритмом Дэйстри. Программный комплекс решает задачу поиска самого...

Поиск кратчайшего пути в матрице через рекурсию - C++
Есть задача: найти кратчайший путь в матрице,представляющий из себя сумму значений ее элементов. Матрица размера 10х10. Я реализовал сам...

Порядок вершин при поиске кратчайшего пути - C++
Есть алгоритм Дейкстры для поиска кратчайшего пути между вершинами. Прога ищет путь правильно и выдает число равное длине минимального...

Поиск кратчайшего пути между вершинами на основе очереди - C++
Задан ориентированный граф вида матрицы смежности. Нужно определить кратчайшее расстояние от одной вершины к другой. Вход: 4 1 2 -...

Нахождение кратчайшего пути от одной вершины графа до другой - C++
Парни помогите доделать , в общем дан граф , я представил его связи в виде матрицы смежностей #include &lt;iostream.h&gt; #include...

Нахождение кратчайшего пути в неорентированном графе от заданой вершины к заданной - C++
Добрый день. Вот решаю задачку о кратчайщем расстояние между двумя верщинами в неорентированном связном графе без циклов. Заданны такие...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
shmkv
562 / 276 / 37
Регистрация: 21.07.2015
Сообщений: 845
29.07.2015, 14:16     Задача нахождения кратчайшего пути #2
Simix, ну увидел три момента (может их больше):
1. Не запоминается уже пройденные клетки, т.е. робот может ходить циклически.
2. Со сдвигами указателя на матрицу ты перемудрил - у тебя при последующих итерация рекурсии матрица всегда сдвигается, а это вообще может привести выходу за пределы массива. Про корректность я вообще молчу.
3. Какая-то путаница в названии переменных и комментариях с поиском то ли минимальной то ли максимальной суммы. Судя по коду ищешь в все-таки максимальную.
MansMI
1137 / 934 / 240
Регистрация: 08.01.2012
Сообщений: 3,392
29.07.2015, 20:29     Задача нахождения кратчайшего пути #3
Сообщение было отмечено автором темы, экспертом или модератором как ответ
если еще интересно:
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
struct cell{ int n,s,m; };
//cells, row, col,step, cursum, maxsum
void treasure(cell cl[][6], int r, int c, int s, int sum, int *max)
{
    cl[r][c].s=s;
    sum+=cl[r][c].n;
    if(!r && c==5)
    {
        if(sum>*max)
        {
            for(int i=0; i<6; i++)
                for(int j=0; j<6; j++) cl[i][j].m=cl[i][j].s;
            *max=sum;
        }
    }
    else
    if(s<17)
    {
        int dr[]={-1, 0, 1, 0};
        int dc[]={ 0, 1, 0,-1};
        for(int i=0; i<4; i++)
        {
            int nr=r+dr[i];
            int nc=c+dc[i];
            if(nr>=0 && nr<6 && nc>=0 && nc<6 && !cl[nr][nc].s)
                treasure(cl, nr, nc, s+1, sum, max);
        }
    }
    cl[r][c].s=0;
}
 
void main()
{
    int a[6][6]={{ 0,10, 0, 1, 0, 0}, { 3, 0, 4, 0, 1, 0},
                 { 7, 0, 0, 4, 0, 0}, { 0, 0, 3, 0, 0, 5},
                 { 0, 6, 0, 2, 0, 0}, { 0, 0, 3, 0, 9, 6}};
    cell c[6][6];
 
    for(int i=0; i<6; i++)
        for(int j=0; j<6; j++)
        {
            c[i][j].n=a[i][j];
            c[i][j].s=0;
        }
    
    int max=0;
    treasure(c,5,0,1,0,&max);
 
    for(int i=0; i<6; i++)
    {
        for(int j=0; j<6; j++) printf("%3d",c[i][j].m);
        printf("\n");
    }
    printf("%d\n",max);
    system("pause");
}
Simix
0 / 0 / 0
Регистрация: 13.04.2015
Сообщений: 3
30.07.2015, 18:58  [ТС]     Задача нахождения кратчайшего пути #4
MansMI, огромное спасибо, выручил. Теперь понял, как решать задачи такого типа.
Yandex
Объявления
30.07.2015, 18:58     Задача нахождения кратчайшего пути
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru