Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Simix
0 / 0 / 0
Регистрация: 13.04.2015
Сообщений: 3
#1

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

29.07.2015, 13:57. Просмотров 676. Ответов 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;
}

http://www.cyberforum.ru/cpp-beginners/thread1852315.html
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.07.2015, 13:57
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Задача нахождения кратчайшего пути (C++):

Задача (вывести длину кратчайшего пути от точки до точки.)
Пишу задачу, нужно вывести длину кратчайшего пути от точки до точки. ...

Нахождение кратчайшего пути
Нужно сделать программу,чтоб она находила кратчайший путь от города 1 до города...

Поиск кратчайшего пути на графе
Выдает ошибку Error 1 error C4996: 'itoa': The POSIX name for this item is...

Поиск кратчайшего пути в графе
Задача: отыскать кратчайший путь между двумя заданными вершинами в произвольном...

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

3
shmkv
652 / 371 / 57
Регистрация: 21.07.2015
Сообщений: 1,059
29.07.2015, 14:16 #2
Simix, ну увидел три момента (может их больше):
1. Не запоминается уже пройденные клетки, т.е. робот может ходить циклически.
2. Со сдвигами указателя на матрицу ты перемудрил - у тебя при последующих итерация рекурсии матрица всегда сдвигается, а это вообще может привести выходу за пределы массива. Про корректность я вообще молчу.
3. Какая-то путаница в названии переменных и комментариях с поиском то ли минимальной то ли максимальной суммы. Судя по коду ищешь в все-таки максимальную.
0
MansMI
1447 / 1156 / 549
Регистрация: 08.01.2012
Сообщений: 4,509
29.07.2015, 20:29 #3
Лучший ответ Сообщение было отмечено Simix как решение

Решение

если еще интересно:
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");
}
1
Simix
0 / 0 / 0
Регистрация: 13.04.2015
Сообщений: 3
30.07.2015, 18:58  [ТС] #4
MansMI, огромное спасибо, выручил. Теперь понял, как решать задачи такого типа.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2015, 18:58
Привет! Вот еще темы с решениями:

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

Поиск кратчайшего пути в графе
Добрый вечер! Помогите решить задание пожалуйста: написать программу, решающую...

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

Нахождение кратчайшего пути, поиск с возвратом
Описание проблемы: Есть матрица MxN, на матрицы есть дом школьника и школа....


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

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