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

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

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

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

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

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

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

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

3
shmkv
1199 / 421 / 59
Регистрация: 21.07.2015
Сообщений: 1,110
29.07.2015, 14:16 2
Simix, ну увидел три момента (может их больше):
1. Не запоминается уже пройденные клетки, т.е. робот может ходить циклически.
2. Со сдвигами указателя на матрицу ты перемудрил - у тебя при последующих итерация рекурсии матрица всегда сдвигается, а это вообще может привести выходу за пределы массива. Про корректность я вообще молчу.
3. Какая-то путаница в названии переменных и комментариях с поиском то ли минимальной то ли максимальной суммы. Судя по коду ищешь в все-таки максимальную.
0
MansMI
1448 / 1157 / 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

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

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

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


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

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

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