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

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

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

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

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

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

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

Определить позиции запятых - C++
Дано строчку символов, содержащий комы. Определить, на какой позиции находится первая и последняя по порядку кома

Определить позицию, с которой подстрока входит в строку - C++
не работает программа, выдает ошибки помогите плз // Лабораторная работа №3 // Массивы // #include "stdafx.h" #include...

Определить позицию последнего минимального элемента массива - C++
Дан массив A(N). Надо определить место маленького последнего элемента.

Определить позицию первого и последнего нуля в одномерном массиве - C++
Определить позицию первого и последнего нуля в одномерном массиве, использую цикл For. Например массив состоит из 10307, программа в ответе...

Определить последний отрицательный максимальный элемент и его позицию в массиве - C++
мальчики помогите пожалуйста решить задачи 1)Для заданного двумерного массива из n строк и m столбцов: a.)Определить последний...

Определить в матрице минимальное и максимальное значение и их позиции - C++
помогите написать код...я просто в этом не очень разбираюсь...буду очень благодарен за помощь Постановка задачи: Выполнить...

Определить значения и позиции первого и последнего положительного - C++
Ребят,что в этой программе не так?Будьте добры,подскажите. //Дан массив типа double. Определить значения и позиции первого //и...

Определить какой символ стоит на позиции с номером n - C++
Задача В игре участвуют двое – А и Б, каждый по очереди ставит свой символ в строку, причем переписывает все что было написано до него...

Определить позицию первого вхождения в заданную строку какого-либо символа - 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     Определить маршрут робота из позиции (хс, ус) в позицию (хф, уф)
Ответ Создать тему
Опции темы

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