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

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

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

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

29.07.2015, 13:57. Просмотров 523. Ответов 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
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача нахождения кратчайшего пути (C++):

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

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

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

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

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

Поиск кратчайшего пути на графе - C++
Выдает ошибку Error 1 error C4996: 'itoa': The POSIX name for this item is deprecated. Instead, use the ISO C++ conformant name: _itoa. See...

3
shmkv
622 / 337 / 43
Регистрация: 21.07.2015
Сообщений: 992
29.07.2015, 14:16 #2
Simix, ну увидел три момента (может их больше):
1. Не запоминается уже пройденные клетки, т.е. робот может ходить циклически.
2. Со сдвигами указателя на матрицу ты перемудрил - у тебя при последующих итерация рекурсии матрица всегда сдвигается, а это вообще может привести выходу за пределы массива. Про корректность я вообще молчу.
3. Какая-то путаница в названии переменных и комментариях с поиском то ли минимальной то ли максимальной суммы. Судя по коду ищешь в все-таки максимальную.
0
MansMI
1295 / 1073 / 299
Регистрация: 08.01.2012
Сообщений: 4,080
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");
}
1
Simix
0 / 0 / 0
Регистрация: 13.04.2015
Сообщений: 3
30.07.2015, 18:58  [ТС] #4
MansMI, огромное спасибо, выручил. Теперь понял, как решать задачи такого типа.
0
30.07.2015, 18:58
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2015, 18:58
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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