Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Форум программистов и сисадминов Киберфорум > Форум программистов > C/C++ > C++ > С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.56/9: Рейтинг темы: голосов - 9, средняя оценка - 4.56
 Аватар для SaynorPRO
11 / 11 / 5
Регистрация: 05.10.2016
Сообщений: 122

Кратчайший путь из одной вершины в другую с условием, что двигаться можно только прямо и вправо

15.02.2017, 18:47. Показов 1925. Ответов 2
Метки нет (Все метки)
Студворк — интернет-сервис помощи студентам
Задача

Условие
Змей Горыныч оказался в лабиринте и хочет выбраться из него как можно скорее. К сожалению, после вчерашнего употребления кефира, левая голова Змея соображает плохо. Поэтому Змей Горыныч может поворачивать направо и идти прямо, но не может поворачивать налево и разворачиваться на месте. Помогите Змею Горынычу определить длину кратчайшего пути до выхода из лабиринта.

Входные данные
В первой строке через пробел записаны числа r и c (4 ≤ r, c ≤ 20) - количество строк и столбцов в карте лабиринта. В каждой из следующих r строк записано по c символов, задающих эту карту. Символ S обозначает положение Змея Горыныча, символ F - точку выхода из лабиринта, символ X - стенку. Пробелами обозначены проходимые клетки. Гарантируется, что лабиринт окружен стенами. Перед началом движения Змей Горыныч может сориентироваться по любому из 4 направлений (вверх, вниз, влево или направо).

Выходные данные
Выведите единственное число - расстояние, которое придется пройти Змею Горынычу. Гарантируется, что он всегда сможет выйти из лабиринта.

Пример

Входные данные
Code
1
2
3
4
5
6
7
8
9
10
11
12

10 14
XXXXXXXXXXXXXX
X          XXX
X XFXXXXX    X
XXX   XX  XX X
X S          X
XX  XXXXXX X X
X        X X X
X X      X X X
XXX XX       X
XXXXXXXXXXXXXX
(Оформил это как код, чтобы было видно пробелы)


Выходные данные29




Поиск в ширину - сделал, счётчик ходов - сделал, но проблема в другом. Эта проблема особенно видна, если сделать пустое поле максимального размера (20х20), и поставить Змея Горыныча в левый нижний угол, а выход в правый верхний, а потом запустить программу, то после 40 секунд, она вылетит с ошибкой bad_alloc. Да, да, она самая, но на этот раз проблема не в ней, потому что если немного разобраться, всё становится ясно: перед вылетом в очередях более 170 миллионов элементов, и это количество только растёт. Я могу сказать, почему. У моей программы нет тормозов. Я не могу придумать правило, которое не даст Змею Горынычу делать ненужные движения. Вернее могу, я придумал, даже несколько, но все они не работают. В коде я вам представил самое, на мой взгляд, удачное решение, к которму я не могу придумать контр-тесты, но сайт его бракует, выдавая два правильных ответа из семи. Это первая и единственная проблема, которую я заметил.

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

#include <fstream>
#include <queue>
#include <vector>
 
 
using namespace std;
 
ifstream in ("input.txt");
ofstream out ("output.txt");
 
const int MAX = 21;
int start_i = 0, start_j = 0, finish_i = 0, finish_j = 0;
 
 
 
void labyrinthRead(int r, int c, int labyrinth[][MAX]) {
  FILE *fp = fopen("input.txt", "r");
  if (r < 10 && c < 10) {
    fseek(fp, 5, SEEK_SET);
  }
  if ((r >= 10 && c < 10) || (r < 10 && c >= 10)) {
    fseek(fp, 6, SEEK_SET);
  }
  if (r >= 10 && c >= 10) {
    fseek(fp, 7, SEEK_SET);
  }
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < c + 1; j++) {
      char ch;
      ch = getc(fp);
      switch(ch) {
        case 'X': {
          labyrinth[i][j] = -1;
          break;
        }
        case ' ': {
          labyrinth[i][j] = 0;
          break;
        }
        case 'F': {
          labyrinth[i][j] = 1;
          finish_i = i;
          finish_j = j;
          break;
        }
        case 'S': {
          labyrinth[i][j] = 0;
          start_i = i;
          start_j = j;
          break;
        }
      }
    }
  }
}
 
void pushSides(queue<int> *q_i, queue<int> *q_j, queue<int> *q_side, int positions[][MAX], int labyrinth[][MAX]) {
  int i = q_i->front();
  int j = q_j->front();
  int side = q_side->front();
  switch (side) {
      case 1: {
        if (labyrinth[i][j-1] != -1/* && positions[i][j-1] != side*/) {
          q_i->push(i);
          q_j->push(j - 1);
          q_side->push(side);
          //positions[i][j-1] = side;
          labyrinth[i][j-1] = labyrinth[i][j] + 1;
        }
        if (labyrinth[i-1][j] != -1/* && positions[i-1][j] != 2*/) {
          q_i->push(i - 1);
          q_j->push(j);
          q_side->push(2);
          //positions[i-1][j] = 2;
          labyrinth[i-1][j] = labyrinth[i][j] + 1;
        }
        break;
    }
     case 2: {
        if (labyrinth[i-1][j] != -1/* && positions[i-1][j] != side*/) {
          q_i->push(i - 1);
          q_j->push(j);
          q_side->push(side);
          //positions[i-1][j] = side;
          labyrinth[i-1][j] = labyrinth[i][j] + 1;
        }
        if (labyrinth[i][j+1] != -1/* && positions[i][j+1] != 3*/) {
          q_i->push(i);
          q_j->push(j + 1);
          q_side->push(3);
          //positions[i][j+1] = 3;
          labyrinth[i][j+1] = labyrinth[i][j] + 1;
        }
        break;
    }
     case 3: {
        if (labyrinth[i][j+1] != -1/* && positions[i][j+1] != side*/) {
          q_i->push(i);
          q_j->push(j + 1);
          q_side->push(side);
          //positions[i][j+1] = side;
          labyrinth[i][j+1] = labyrinth[i][j] + 1;
        }
        if (labyrinth[i+1][j] != -1/* && positions[i+1][j] != 4*/) {
          q_i->push(i + 1);
          q_j->push(j);
          q_side->push(4);
          //positions[i+1][j] = 4;
          labyrinth[i+1][j] = labyrinth[i][j] + 1;
        }
        break;
    }
     case 4: {
        if (labyrinth[i+1][j] != -1/* && positions[i+1][j] != side*/) {
          q_i->push(i + 1);
          q_j->push(j);
          q_side->push(side);
          //positions[i+1][j] = side;
          labyrinth[i+1][j] = labyrinth[i][j] + 1;
        }
        if (labyrinth[i][j-1] != -1/* && positions[i][j-1] != 1*/) {
          q_i->push(i);
          q_j->push(j - 1);
          q_side->push(1);
          //positions[i][j-1] = 1;
          labyrinth[i][j-1] = labyrinth[i][j] + 1;
        }
        break;
    }
  }
}
 
int bfs(int labyrinth[][MAX] ){
  queue<int> q_i;
  queue<int> q_j;
  queue<int> q_side;
  int positions[MAX][MAX] = {{}};
  for (int i = 1; i < 5; i++) {
    q_i.push(start_i);
    q_j.push(start_j);
    q_side.push(i);
  }
  int i, j;
  while (i != finish_i || j != finish_j) {
    i = q_i.front();
    j = q_j.front();
    pushSides(&q_i, &q_j, &q_side, positions, labyrinth);
    q_i.pop();
    q_j.pop();
    q_side.pop();
  }
  return labyrinth[finish_i][finish_j];
}
 
 
int main() {
  int labyrinth[MAX][MAX] = {};
  static int r = 0, c = 0;
  in >> r >> c;
  labyrinthRead(r, c, labyrinth);
  int steps = bfs(labyrinth);
  out << steps << endl;
  return 0;
}
(Это решение задачи БЕЗ сдерживания Змея Горыныча, чтобы активировать правило, просто уберите все комментарии)

Теперь постараюсь объяснить мой код. Начну снизу вверх.
1. Функция labyrinthRead
Функция labyrinthRead необходима для правильного чтения массива. Она сдвигает каретку на начало поля и начинает считывать посимовльно. В зависимости от символа, вставляет в массив labyrinth нужную цифру.
-1 - если стенка
0 - если пустое место, или там стоит Змей Горыныч (так же записывает координаты в start_i и start_j)
1 - если здесь стоит выход (так же записывает координаты в finish_i и finish_j)
2. Функция pushSides
Здесь уже сложнее. Так как правая сторона будет разной относительно тех сторон, куда повёрнута голова Змея Горыныча. Я решил их пронумеровать вот так Вложение 799192
Стрелка - это сторона, в которую повёрнута голова Змея, соответственно для каждой стороны своя правая сторона.
В функцию я передал три очереди, первые две - координаты, третья - сторона, в которую при этом должен быть повёрнут Змей Горыныч. Далее, функция, в зависимости от стороны side, проверяет, есть ли на пути стена и добавляет две пары координат, прямо и направо.
3.Функция bfs
Тут всё просто: беру вершину, записываю для неё пару вершин, удаляю эту вершину. И так, пока не найду выход

Объясняю правило
Тупым правилом "был в этой клетке, значит больше и не надо в ней быть" здесь не обойтись. Как видно по примеру в условии, он должен и будет наматывать круги по всей площади. Так что я не смог придумать ничего лучше, как записывать в отдельный массив positions ту позицию, из которой я в него попал. И сделать проверку: если позиция из которой туда попали совпадает с текущей, то условие ложно и в очередь ничего не добавляется.

Сидел над этой задачей часов восемь. Перепроверил всё что только можно(и ещё раз проверил в процессе написания этого поста), надеюсь на вашу помощь.

Добавлено через 5 минут
Тест на котором программа не идёт
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

20 20
XXXXXXXXXXXXXXXXXXXX
X                 FX
X                  X
X                  X
X                  X
X                  X
X                  X
X                  X
X                  X
X                  X
X                  X
X                  X
X                  X
X                  X
X                  X
X                  X
X                  X
X                  X
XS                 X
XXXXXXXXXXXXXXXXXXXX
После активации этого правила проблема с этим тестом пропадает, но сайт как не брал, так продолжает её не брать.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
 15.02.2017, 18:47
Ответы с готовыми решениями:

С помощью метода волны найти кратчайший путь из одной клетки в другую (ход конём)
Пытаюсь решить такую задачу: с помощью метода волны нужно найти кратчайший путь из одной клетки в другую. Проблема состоит в том, что я...

Найти кратчайший путь из вершины u в вершину v
Уффф, к завтрашнему дню нужно сдать эти задачи, помогите пожалуйста кто чем сможет :sorry: (следующие задачи через обходы в глубину и...

Алгоритм Дейкстры - Найти кратчайший путь от 1 вершины
Вот рисунок по которому нада найти кратчайший путь от 1 вершины помагите плизз

2
 Аватар для SaynorPRO
11 / 11 / 5
Регистрация: 05.10.2016
Сообщений: 122
15.02.2017, 18:49  [ТС]
Почему-то скриншот не отобразился, вот он:Название: Безымянный.png Просмотров: 72 Размер: 4.0 Кб
0
 Аватар для SaynorPRO
11 / 11 / 5
Регистрация: 05.10.2016
Сообщений: 122
18.02.2017, 22:32  [ТС]
Задача решена, проблема была в функции labyrinthRead.
Эта часть оказалась проблемной
C++
1
2
3
4
5
6
7
8
9
10

FILE *fp = fopen("input.txt", "r");
  if (r < 10 && c < 10) {
    fseek(fp, 5, SEEK_SET);
  }
  if ((r >= 10 && c < 10) || (r < 10 && c >= 10)) {
    fseek(fp, 6, SEEK_SET);
  }
  if (r >= 10 && c >= 10) {
    fseek(fp, 7, SEEK_SET);
  }
Вот рабочий код

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

#include <fstream>
#include <queue>
#include <vector>
#include <iomanip>
#include <algorithm>
 
using namespace std;
 
ifstream in ("input.txt");
ofstream out ("output.txt");
 
const int MAX = 21;
int start_i = 0, start_j = 0, finish_i = 0, finish_j = 0;
 
 
 
void labyrinthRead(int r, int c, int labyrinth[][MAX]) {
  in.get();
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < c + 1; j++) {
      char ch;
      ch = in.get();
      switch(ch) {
        case 'X': {
          labyrinth[i][j] = -1;
          break;
        }
        case ' ': {
          labyrinth[i][j] = 0;
          break;
        }
        case 'F': {
          labyrinth[i][j] = 1;
          finish_i = i;
          finish_j = j;
          break;
        }
        case 'S': {
          labyrinth[i][j] = 0;
          start_i = i;
          start_j = j;
          break;
        }
      }
    }
  }
}
 
void pushSides(queue<int> *q_i, queue<int> *q_j, queue<int> *q_side, int positions[][MAX], int labyrinth[][MAX]) {
  int i = q_i->front();
  int j = q_j->front();
  int side = q_side->front();
  switch (side) {
      case 1: {
        if (labyrinth[i][j-1] != -1 && positions[i][j-1] != side) {
          q_i->push(i);
          q_j->push(j - 1);
          q_side->push(side);
          positions[i][j-1] = side;
          labyrinth[i][j-1] = labyrinth[i][j] + 1;
        }
        if (labyrinth[i-1][j] != -1 && positions[i-1][j] != 2) {
          q_i->push(i - 1);
          q_j->push(j);
          q_side->push(2);
          positions[i-1][j] = 2;
          labyrinth[i-1][j] = labyrinth[i][j] + 1;
        }
        break;
    }
     case 2: {
        if (labyrinth[i-1][j] != -1 && positions[i-1][j] != side) {
          q_i->push(i - 1);
          q_j->push(j);
          q_side->push(side);
          positions[i-1][j] = side;
          labyrinth[i-1][j] = labyrinth[i][j] + 1;
        }
        if (labyrinth[i][j+1] != -1 && positions[i][j+1] != 3) {
          q_i->push(i);
          q_j->push(j + 1);
          q_side->push(3);
          positions[i][j+1] = 3;
          labyrinth[i][j+1] = labyrinth[i][j] + 1;
        }
        break;
    }
     case 3: {
        if (labyrinth[i][j+1] != -1 && positions[i][j+1] != side) {
          q_i->push(i);
          q_j->push(j + 1);
          q_side->push(side);
          positions[i][j+1] = side;
          labyrinth[i][j+1] = labyrinth[i][j] + 1;
        }
        if (labyrinth[i+1][j] != -1 && positions[i+1][j] != 4) {
          q_i->push(i + 1);
          q_j->push(j);
          q_side->push(4);
          positions[i+1][j] = 4;
          labyrinth[i+1][j] = labyrinth[i][j] + 1;
        }
        break;
    }
     case 4: {
        if (labyrinth[i+1][j] != -1 && positions[i+1][j] != side) {
          q_i->push(i + 1);
          q_j->push(j);
          q_side->push(side);
          positions[i+1][j] = side;
          labyrinth[i+1][j] = labyrinth[i][j] + 1;
        }
        if (labyrinth[i][j-1] != -1 && positions[i][j-1] != 1) {
          q_i->push(i);
          q_j->push(j - 1);
          q_side->push(1);
          positions[i][j-1] = 1;
          labyrinth[i][j-1] = labyrinth[i][j] + 1;
        }
        break;
    }
  }
}
 
int bfs(int labyrinth[][MAX] ){
  queue<int> q_i;
  queue<int> q_j;
  queue<int> q_side;
  int positions[MAX][MAX] = {{}};
  for (int i = 1; i < 5; i++) {
    q_i.push(start_i);
    q_j.push(start_j);
    q_side.push(i);
  }
  int i, j;
  while (i != finish_i || j != finish_j) {
    i = q_i.front();
    j = q_j.front();
    pushSides(&q_i, &q_j, &q_side, positions, labyrinth);
    q_i.pop();
    q_j.pop();
    q_side.pop();
  }
  return labyrinth[finish_i][finish_j];
}
 
 
int main() {
  int labyrinth[MAX][MAX] = {};
  static int r = 0, c = 0;
  in >> r >> c;
  labyrinthRead(r, c, labyrinth);
  int steps = bfs(labyrinth);
  out << steps << endl;
  return 0;
}
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
 18.02.2017, 22:32
Помогаю со студенческими работами здесь

Определить кратчайший путь от начальной вершины к конечной
определить кратчайший путь от начальной вершины к конечной. заполнить ленточную матрицу шириной 3, нормальное распределение. у меня 8...

Программа, способная отвечать на запросы и возвращать кратчайший путь до заданной вершины
Всем доброго времени суток! помогите пожалуйста реализовать код на Haskell &quot;программа, способная отвечать на запросы и возвращать...

Найти кратчайший путь от одной точки параллелепипеда до другой
Задача выглядит так: На поверхности прямоугольного параллелепипеда сидит муха и нанесена капля варенья. Определите наименьшее...

Как создать ограничение для ScrollBar? Например, чтобы можно было вправо прокрутить только 3 раза (нажать вправо мышкой только 3 раза, а дальше нельзя
Как создать ограничение для ScrollBar? Например, чтобы можно было вправо прокрутить только 3 раза (нажать вправо мышкой только 3 раза, а...

Как только что установлений AUTO_INCREMENT записать из одной таблици в другую?
Есть запрос: $query=mysql_query(&quot;INSERT INTO `database`.`client` (`code_client`, `name`, `code_region`, `street`, `home`, `room`,...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Новые блоги и статьи
http://iceja.net/ сервер решения полиномов
iceja 18.01.2026
Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Первый деплой
lagorue 16.01.2026
Не спеша развернул своё 1ое приложение в kubernetes. А дальше мне интересно создать 1фронтэнд приложения и 2 бэкэнд приложения развернуть 2 деплоя в кубере получится 2 сервиса и что-бы они. . .
Расчёт переходных процессов в цепи постоянного тока
igorrr37 16.01.2026
/ * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит: токи, напряжения и их 1 и 2 производные при t = 0;. . .
Восстановить юзерскрипты Greasemonkey из бэкапа браузера
damix 15.01.2026
Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Изучаю kubernetes
lagorue 13.01.2026
А пригодятся-ли мне знания kubernetes в России?
 Сукцессия микоризы: основная теория в виде двух уравнений.
anaschu 11.01.2026
https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
WordPad для Windows 11
Jel 10.01.2026
WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
Classic Notepad for Windows 11
Jel 10.01.2026
Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Поддержать - Реклама - Условия использования - Обратная связь
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru