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

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

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

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

11.12.2012, 17:36. Просмотров 481. Ответов 5
Метки нет (Все метки)

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

Кратчайший маршрут робота - PascalABC.NET
Нужно написать программу для определения маршрута робота.В клеточном поле двигается робот. Имеется система координат x и y (номер клетки по...

Вывести на экран компьютера маршрут движения робота - Turbo Pascal
Петя вместе со своим другом Пашей решили создать программу для урока информатики по теме "Моделирование". За основу работы они решили взять...

Определите маршрут каравана из одной позиции в другую - Pascal ABC
Помогите решить задачу. Заранее спасибо. Имеется план местности, разбитой на квадраты, который задан матрицей размера N×N. Каждый...

Как узнать позицию текста по позиции курсора? - jQuery
Имеется html-код страницы в блоке <pre></pre>, который выводится на экран со всеми отступами,т.е. отформатирован. Нужно по заданному...

Извлечь 3 бита целого числа A с позиции n и перенести в число B на позицию m - C++
Доброго времени суток.Дана вот такая задача : извлечь 3 бита числа А, начиная с позиции n, и вставить их в число В, начиная с позиции...

При наведении курсора на определённую позицию в заказе появляется всплывающая подсказка (по позиции) - JavaScript
В скрипте информация представляется в иерархической структуре (контракт – цех – заказ - позиция) При наведении курсора на...

5
Stasq329
0 / 0 / 0
Регистрация: 01.05.2014
Сообщений: 15
28.05.2014, 20:08 #2
решил? нужна таже задача.
0
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;
}
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
как исправить ошибки?
0
nadegdak
0 / 0 / 0
Регистрация: 11.12.2012
Сообщений: 3
28.05.2014, 23:00  [ТС] #5
Она вроде рабочая
по крайней мере у меня запускалась
0
Stasq329
0 / 0 / 0
Регистрация: 01.05.2014
Сообщений: 15
28.05.2014, 23:27 #6
какая-то хрень. он при компиляции проходит, но на запуске ошибка
0
28.05.2014, 23:27
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.05.2014, 23:27
Привет! Вот еще темы с ответами:

Вставьте порядковый номер максимального элемента за ним. передвинув все оставшиеся позиции на одну позицию впр - Turbo Pascal
Здравствуйте! Прошу помощи в дописании программы:( В одномерном массиве найти максимальный элемент. Вставьте порядковый номер...

Однонаправленный список. Операции: удалить элемент из заданной позиции, добавить элемент в заданную позицию,проверка на неравенство - C++
Помогите. Есть одна написанная. Условия: Очередь. Операции: “+” добавить элемент ; “-“ удалить элемент ; bool() проверка «Пуста...

Определить маршрут движения. - Prolog
Задача: Создать БД с расписанием движения самолетов: Номер рейса, Пункт отправления, Пункт прибытия, ...

Определить является ли маршрут на графе цепью - Lisp
Добрый день! Помогите пожалуйста решить задачу))) Маршрут на графе задается списком ((a c) (c e) (e d) (d c) (c b) (b a) (a c)), где (a...


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

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

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