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

Определить маршрут робота из позиции (хс, ус) в позицию (хф, уф) - C++

Восстановить пароль Регистрация
 
nadegdak
0 / 0 / 0
Регистрация: 11.12.2012
Сообщений: 3
11.12.2012, 17:36     Определить маршрут робота из позиции (хс, ус) в позицию (хф, уф) #1
Имеется план местности, разбитой на квадраты, заданный матрицей размером NxN. Каждый квадрат имеет высоту относительно уровня моря, значение которой определяется натуральным числом. Необходимо определить маршрут робота из позиции (ХС, УС) в позицию (ХФ, УФ), при котором суммарная длина его маршрута минимальна. Длина маршрута определяется как суммарная длина подъемов и спусков плюс суммарная длина перемещений из квадрата в квадрат. Робот может двигаться только по местности и только параллельно осям Ох и Оy между центрами квадратов. При переходе в соседний квадрат длина подъема (спуска) равна модулю разности высот квадратов, а длина перемещения из квадрата в квадрат равна величине К.
План местности - матрица, эл. кот. - высоты квадратов.
Вопрос именно в том, как сделать эту задачу через очереди или стеки.
Помогите плиз
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.12.2012, 17:36     Определить маршрут робота из позиции (хс, ус) в позицию (хф, уф)
Посмотрите здесь:

C++ Определить последний отрицательный максимальный элемент и его позицию в массиве
Определить позиции SelStart'a C++
Вычислить сумму ряда с позиции N до позиции M. Функцию вычисления суммы реализовать рекурсивно. C++
Определить в матрице минимальное и максимальное значение и их позиции C++
Определить позицию первого и последнего нуля в одномерном массиве C++
C++ Однонаправленный список. Операции: удалить элемент из заданной позиции, добавить элемент в заданную позицию,проверка на неравенство
Определить какой символ стоит на позиции с номером n C++
C++ Определить позиции запятых
Определить значения и позиции первого и последнего положительного C++
C++ Определить позицию, с которой подстрока входит в строку
C++ Извлечь 3 бита целого числа A с позиции n и перенести в число B на позицию m
Определить позицию последнего минимального элемента массива C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Stasq329
0 / 0 / 0
Регистрация: 01.05.2014
Сообщений: 15
28.05.2014, 20:08     Определить маршрут робота из позиции (хс, ус) в позицию (хф, уф) #2
решил? нужна таже задача.
nadegdak
0 / 0 / 0
Регистрация: 11.12.2012
Сообщений: 3
28.05.2014, 21:08  [ТС]     Определить маршрут робота из позиции (хс, ус) в позицию (хф, уф) #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
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include <iostream>
using namespace std;
struct Queue
{
    int *x;
    int *y;
    int front;
    int rear;
};
Queue step;
struct way
{
    int Ox;
    int Oy;
    int Old_metk;
    int old_Ox;
    int old_Oy;
};
way Way[200]={0};
void push_puc(int x,int y, int old_metk, int old_x, int old_y,int i)
{
    Way[i].Ox=x;
    Way[i].Oy=y;
    Way[i].Old_metk=old_metk;
    Way[i].old_Ox=old_x;
    Way[i].old_Oy=old_y;
}
void create_queue(const int n)
{
    step.x=new int [n*n];
    step.y=new int [n*n];
    step.front=0;
    step.rear=0;
}
void delete_queue()
{
    delete [] step.x;
    delete [] step.y;
}
void push(int x, int y, int n)
{
    if ((step.rear+1==step.front) || ((step.rear==n*n) && (step.front==0)))
        throw "Очередь заполнена";
    step.x[step.rear]=x;
    step.y[step.rear]=y;
    step.rear++;
    if (step.rear>n*n)
        step.rear=0;
}
bool pop(int &x, int &y,int n)
{
    if (step.rear==step.front)
        return false;
    x=step.x[step.front];
    y=step.y[step.front];
    step.front++;
    if (step.front>n*n)
        step.front=0;
    return true;
}
int**Read_Plan(int &n)
{
    FILE *in;
    if (!(in=fopen("karta.txt","rt")))
        throw "Невозможно открыть входной файл!"; 
    fscanf(in, "%d",&n);
    if (feof(in))
        throw "Файл пустой";
    int**matr;
    matr=new int*[n];
    for (int i=0; i<n; i++)
        matr[i]=new int[n];
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            fscanf(in, "%d", &matr[i][j]);
    fclose(in);
    return matr;
}
int main()
{
    try{
    setlocale(LC_ALL,".1251");
    FILE  *in,*out;
    int **a,**metk;
    int n,i,j,k;
    int x1,x2,y1,y2,x,y;
    int count,first_metk=0,temp;
    int main_wayx[200]={0};
    int main_wayy[200]={0};
    cout<<"Введите длину перемещений между квадратами"<<endl;
    cin>>k;
    cout<<"Введите начальные координаты"<<endl;
    cin>>x1>>y1;
    cout<<"Введите конечные координаты"<<endl;
    cin>>x2>>y2;
    a=Read_Plan(n); 
    first_metk=INT_MAX;
    for(i=0; i<n/2; i++)
        swap(a[i],a[n-i-1]);
    for(i=0; i<n-1; i++)
        for(j=i+1; j<n; j++)
            swap(a[i][j],a[j][i]);
    metk=new int*[n];
    for (i=0; i<n; i++)
        metk[i]=new int[n];
    for (i=0; i<n; i++)
        for (j=0; j<n; j++)
            metk[i][j]=first_metk;
    metk[x1][y1]=0;
    create_queue(n);
    i=0;
    push(x1,y1,n);
    while(pop(x,y,n))   
    {
        if (((count=x+1)<n) && (metk[count][y]>(metk[x][y]+abs(a[x][y]-a[count][y])+k)))
        {
            metk[count][y]=metk[x][y]+abs(a[x][y]-a[count][y])+k;
            push(count,y,n);
            push_puc(count,y,metk[count][y],x,y,i); i++;    
        }
        if (((count=x-1)>=0) && (metk[count][y]>(metk[x][y]+abs(a[x][y]-a[count][y])+k)))
        {
            metk[count][y]=metk[x][y]+abs(a[x][y]-a[count][y])+k;
            push(count,y,n);
            push_puc(count,y,metk[count][y],x,y,i); i++;
        }
        if (((count=y-1)>=0) && (metk[x][count]>(metk[x][y]+abs(a[x][y]-a[x][count])+k)))
        {
            metk[x][count]=metk[x][y]+abs(a[x][y]-a[x][count])+k;
            push(x,count,n);
            push_puc(x,count,metk[x][count],x,y,i); i++;
        }
        if (((count=y+1)<n) && (metk[x][count]>(metk[x][y]+abs(a[x][y]-a[x][count])+k)))
        {
            metk[x][count]=metk[x][y]+abs(a[x][y]-a[x][count])+k;
            push(x,count,n);
            push_puc(x,count,metk[x][count],x,y,i); i++;
        }
    }
    temp=i;
    if(!(out=fopen("output.txt","wt"))) { cout<<"Can't create file!\n"; return -1; }
    fprintf(out,"%d\n",metk[x2][y2]);
    fprintf(out,"%d %d\n",x1,y1);
    j=0;
    for (i=temp-1; i>=0; i--)
        if ((Way[i].Ox==x2) && (Way[i].Oy==y2) && (Way[i].Old_metk==metk[x2][y2]))
        {
            main_wayx[j]=x2;
            main_wayy[j]=y2;
            j++;
            x2=Way[i].old_Ox;
            y2=Way[i].old_Oy;
        }
    temp=j;
    for(j=temp-1; j>=0; j--)
    {
        fprintf(out,"%d %d\n",main_wayx[j], main_wayy[j]);
        a[main_wayx[j]][main_wayy[j]]=0;
        a[x1][y1]=0;
    }
    for(i=0; i<n-1; i++)
        for(j=i+1; j<n; j++)
            swap(a[i][j],a[j][i]);
    for(i=0; i<n/2; i++)
        swap(a[i],a[n-i-1]);
    
    
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
            fprintf(out,"%3d ",a[i][j]);
        fprintf(out,"\n");
    }   
    for (i=0; i<n; i++)
    {
        delete [] a[i];
        delete [] metk[i];
    }
    delete []a;
    delete []metk;
    fclose(out);
    }
    catch(char*k){cout<<k<<endl;}
    return 0;
}
Вложения
Тип файла: txt output.txt (139 байт, 3 просмотров)
Тип файла: txt karta.txt (63 байт, 5 просмотров)
Stasq329
0 / 0 / 0
Регистрация: 01.05.2014
Сообщений: 15
28.05.2014, 22:28     Определить маршрут робота из позиции (хс, ус) в позицию (хф, уф) #4
как исправить ошибки?
nadegdak
0 / 0 / 0
Регистрация: 11.12.2012
Сообщений: 3
28.05.2014, 23:00  [ТС]     Определить маршрут робота из позиции (хс, ус) в позицию (хф, уф) #5
Она вроде рабочая
по крайней мере у меня запускалась
Stasq329
0 / 0 / 0
Регистрация: 01.05.2014
Сообщений: 15
28.05.2014, 23:27     Определить маршрут робота из позиции (хс, ус) в позицию (хф, уф) #6
какая-то хрень. он при компиляции проходит, но на запуске ошибка
Yandex
Объявления
28.05.2014, 23:27     Определить маршрут робота из позиции (хс, ус) в позицию (хф, уф)
Ответ Создать тему
Опции темы

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