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

Кратчайший путь до какой-то координаты. Ошибка std::bad_alloc

08.02.2017, 22:34. Показов 3024. Ответов 33
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Задача
УсловиеНа шахматной доске NxN в клетке (x1, y1) стоит голодный шахматный конь. Он хочет попасть в клетку (x2, y2), где растет вкусная шахматная трава. Какое наименьшее количество ходов он должен для этого сделать?

Входные данныеНа вход программы поступает пять чисел: N, x1, y1, x2, y2 (5 <= N <= 20, 1 <= x1, y1, x2, y2 <= N). Левая верхняя клетка доски имеет координаты (1, 1), правая нижняя - (N, N).

Выходные данныеВ первой строке выведите единственное число K - наименьшее необходимое число ходов коня. В каждой из следующих K+1 строк должно быть записано 2 числа - координаты очередной клетки в пути коня.

Примеры :
Входные данные5
3 3
5 1

Выходные данные4
3 3
2 1
1 3
3 2
5 1

Моё решение :
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
#include <fstream>
#include <queue>
#include <vector>
 
using namespace std;
 
ifstream in ("input.txt");
ofstream out ("output.txt");
 
const int N = 20;
const int neii[8] = {2, 2, -2, -2, 1, -1, -1, 1}; //Два массива, при помощи которых я ищу соседей клетки
const int neij[8] = {-1, 1, -1, 1, -2, -2, 2, 2};  
 
void horseStep(int start_x, int start_y, int finish_x, int finish_y, int pathX[][N], int pathY[][N], int n) {
  queue<int> qi;  //Две очереди с координатами, соседей которых будет проверять алгоритм
  queue<int> qj;
  qi.push(start_y);
  qj.push(start_x);
  int newx = 0, newy = 0;
  int x = 0, y = 0;
  bool used[N][N] = {}; //Массив для точек, в которых побывал конь
  used[start_y][start_x] = true;
  pathX[start_y][start_x] = 0;
  pathX[start_x][start_y] = 0;
  while (!qi.empty() && !qj.empty()) {
    y = qi.front();
    x = qj.front();
    qj.pop();
    qi.pop();
    for (int i = 0; i <= 8; ++i) { //Проверка на выход за границы доски
      if ((x + neij[i] <= n && x + neij[i] >= 0) && (y + neii[i] <= n && y + neii[i] >= 0) && (!used[x+neij[i]][y+neii[i]])) { 
        newx = x + neij[i];        //Прибавляю к координатам значение из соответствующего массива и получаю соседа
        newy = y + neii[i];
        qj.push(newx);
        qi.push(newy);
        used[newy][newx] = true;
        if (pathX[newy][newx] == -1 && pathY[newy][newx] == -1) {
          pathX[newy][newx] = x;
          pathY[newy][newx] = y;
        }
      }
      if (newx == finish_x && newy == finish_y) {
        return;
      }
    }
  }
}
 
void pathRestore(int pathX[][N], int pathY[][N], int start_x, int start_y, int finish_x, int finish_y) {
  int x = finish_x, y = finish_y;
  int newx = 0, newy = 0;
  vector< vector<int> > coord(2);
  while (x != start_y || y != start_x) {
    coord[0].push_back(x + 1);
    coord[1].push_back(y + 1);
    newx = pathX[y][x];
    newy = pathY[y][x];
    x = newx;
    y = newy;
 
  }
  coord[0].push_back(x + 1);
  coord[1].push_back(y + 1);
  out << coord[0].size() - 1 << endl;
  for (int i = coord[0].size() - 1; i != -1; i--) {
    out << coord[0][i] << ' ' << coord[1][i];
    out << endl;
  }
 
}
 
int main() {
  int n;
  in >> n;
  --n;
  int start_x, start_y;
  int finish_x, finish_y;
  in >> start_x >> start_y >> finish_x >> finish_y;
  --start_x; --start_y; --finish_x; --finish_y;
  int pathX[N][N] = {}; //Запись пути, координата Х
  int pathY[N][N] = {}; // Запись пути, координата Y
  fill(&pathX[0][0], &pathX[0][0] + N * N, -1);
  fill(&pathY[0][0], &pathY[0][0] + N * N, -1);
  horseStep(start_x, start_y, finish_x, finish_y, pathX, pathY, n);
  pathRestore(pathX, pathY, start_x, start_y, finish_x, finish_y);
 
  //
  return 0;
}
Проблемы у меня две:
1. При некоторых значениях(например, входной файл: 20 20 20 1 5), после нескольких секунд (от 4 до 40) программа вылетает с такой ошибкой:
Скриншот

2. Сайт почему-то не может её запустить, пишет "Ошибка при выполнении программы", я подозреваю, что это связано с предыдущей проблемой. Хотя тест из условия работает и пара моих тестов тоже.

Если какие-то непонятки с кодом, задавайте вопросы, я всё объясню.

Не по теме:

Что-то мне подсказывает, что всем будет просто впадлу лень ковыряться в моём коде и проблемы я так и не решу, но надежда умирает последней

1
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
08.02.2017, 22:34
Ответы с готовыми решениями:

Ошибка terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc выделение памяти
Уважаемые форумчане! Работаю над программой обработки WAV файлов, но возникла такая проблема: при чтении файла возникает ошибка ...

Ошибка terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc
Есть задача: Написать программу, которая считывает текст из файла и выводит его на экран, заменив цифры от 0 до 9 на слова...

Ошибка terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc
Добрый день!Работаю с графами,и при больших значениях столкнулся с проблемой:ошибка в тесте программы на сайте такова: terminate called...

33
 Аватар для SaynorPRO
11 / 11 / 5
Регистрация: 05.10.2016
Сообщений: 122
10.02.2017, 19:32  [ТС]
Студворк — интернет-сервис помощи студентам
likehood,
Программа вылетает, когда в обеих очередях всего по 57 элементов
Максимум, что я видел в очереди - 81 элемент. Попробуй сам запустить её и посмотреть. Я проверял через size()
0
70 / 70 / 35
Регистрация: 06.07.2016
Сообщений: 415
10.02.2017, 19:35
Ну сделайте вы очередь ручками , это 10 минут занимает. И отлаживайте по-нормальному.
0
1272 / 1029 / 470
Регистрация: 25.12.2016
Сообщений: 3,333
10.02.2017, 19:40
Я бы обернул 34 и 35 строки в блок try-catch, поймал исключение bad_alloc и посмотрел размеры очередей в момент прихода исключения.
0
 Аватар для SaynorPRO
11 / 11 / 5
Регистрация: 05.10.2016
Сообщений: 122
10.02.2017, 20:07  [ТС]
likehood, к сожалению, я новичок и не смог разобраться, как в try-catch-throw засунуть проверку на bad_alloc. Так что, я просто засунул в цикл это:
C++
1
out << qi.size() << ' ' << qj.size() << endl;
Программа, естественно, вылетела, но в файл что-то записала.
Кликните здесь для просмотра всего текста
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
7 7
8 8
9 9
10 10
11 11
12 12
13 13
13 13
14 14
15 15
16 16
17 17
18 18
18 18
19 19
20 20
21 21
22 22
23 23
23 23
24 24
25 25
26 26
27 27
27 27
28 28
29 29
29 29
30 30
30 30
31 31
31 31
31 31
32 32
33 33
34 34
35 35
36 36
37 37
37 37
38 38
39 39
40 40
41 41
41 41
42 42
43 43
44 44
45 45
45 45
46 46
47 47
47 47
48 48
48 48
49 49
49 49
49 49
50 50
51 51
51 51
52 52
53 53
53 53
54 54
54 54
55 55
55 55
56 56
56 56
56 56
57 57
58 58
59 59
60 60
61 61
61 61
62 62
63 63
64 64
65 65
65 65
65 65
66 66
66 66
65 65
66 66
67 67
66 66
67 67
67 67
68 68
67 67
68 68
68 68
67 67
63 63
64 64
65 65
65 65
66 66
66 66
67 67
67 67
68 68
69 69
69 69
70 70
70 70
70 70
70 70
70 70
71 71
70 70
70 70
70 70
71 71
72 72
72 72
72 72
73 73
73 73
72 72
73 73
73 73
72 72
71 71
72 72
72 72
72 72
69 69
70 70
61 61
62 62
63 63
64 64
65 65
66 66
66 66
67 67
68 68
69 69
70 70
70 70
70 70
71 71
71 71
70 70
71 71
72 72
71 71
72 72
72 72
71 71
71 71
70 70
70 70
71 71
65 65
66 66
66 66
66 66
66 66
66 66
67 67
67 67
68 68
65 65
65 65
65 65
65 65
64 64
61 61
57 57
58 58
58 58
58 58
58 58
58 58
56 56
57 57
57 57
57 57
57 57
53 53
52 52
53 53
54 54
55 55
56 56
57 57
57 57
58 58
59 59
60 60
61 61
61 61
61 61
62 62
62 62
61 61
62 62
63 63
62 62
63 63
63 63
62 62
62 62
61 61
61 61
62 62
62 62
58 58
58 58
57 57
56 56
57 57
57 57
57 57
57 57
57 57
56 56
56 56
56 56
56 56
56 56
56 56
57 57
57 57
57 57
56 56
57 57
57 57

Notoriously,
Ну сделайте вы очередь ручками , это 10 минут занимает.
Возможно вы и правы, но я слишком далеко зашёл, я мучаюсь с этой ошибкой уже неделю. У меня с ней уже личные счёты.
И отлаживайте по-нормальному
Буду безмерно благодарен, если объясните, что в вашем понимании "по-нормальному"
0
70 / 70 / 35
Регистрация: 06.07.2016
Сообщений: 415
10.02.2017, 20:11
Цитата Сообщение от SaynorPRO Посмотреть сообщение
я буду благодарен, если ты кто-нибудь объяснит мне, как это возможно дебажить
В очереди, которую вы организуете ручками подобных проблем не будет. Надо же хоть что-то делать с проблемой.
1
 Аватар для SaynorPRO
11 / 11 / 5
Регистрация: 05.10.2016
Сообщений: 122
10.02.2017, 20:30  [ТС]
Notoriously, ради интереса сделал руками. Проблема решилась, ура. Но настроение у меня упало, т.к. я всё ещё не понял, почему при использовании очередей она вылетает? STL контейнеры, их удобство - одна из главных причин, из-за которой я учусь кодить на плюсах. Неужели никто на этом сайте не сталкивался подобной ошибкой?
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13241 / 6873 / 1827
Регистрация: 18.10.2014
Сообщений: 17,422
10.02.2017, 21:08
Цитата Сообщение от SaynorPRO Посмотреть сообщение
Я поторопился. На самом деле не всё так сказочно. Некоторые тесты стали работать, другие - как не работали, так и не работают.
А конкретные входные данные, на которых программа падает, участникам форума предлагается угадать самим?

Добавлено через 14 минут
C++
1
2
      bool beyondCheckX = (x + neij[i] <= n && x + neij[i] >= 0);
      bool beyondCheckY = (y + neii[i] <= n && y + neii[i] >= 0);
Почему проверка на вылет за пределы доски использует нестрогое сравнение на <= n?

Добавлено через 8 минут
Но входе 20, 2, 8, 15, 1 программа вылетает в pathRestore

C++
1
  while (x != start_y || y != start_x) {
из-за того, что в условии продолжения цикла почему-то x сравнивается cо start_y, а y со start_x. Что это за мешанина?
1
 Аватар для SaynorPRO
11 / 11 / 5
Регистрация: 05.10.2016
Сообщений: 122
10.02.2017, 21:09  [ТС]
TheCalligrapher, читайте внимательнее главный пост.
При некоторых значениях(например, входной файл: 20 20 20 1 5), после нескольких секунд (от 4 до 40) программа вылетает с такой ошибкой:
После того, как я обновил код, я не выложил новые данные, при которых программа вылетает. Извиняюсь, моя ошибка(до этого момента, кстати, никто у меня их так и не спросил).

Вот последняя версия кода со встроенными очередями.

Пример данных, с которыми она вылетает : 20 15 14 7 8

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
#include <fstream>
#include <queue>
#include <vector>
 
using namespace std;
 
ifstream in ("input.txt");
ofstream out ("output.txt");
 
const int N = 20;
const int neii[] = {2, 2, -2, -2, 1, -1, -1, 1};
const int neij[] = {-1, 1, -1, 1, -2, -2, 2, 2};
 
void horseStep(int start_x, int start_y, int finish_x, int finish_y, int pathX[][N], int pathY[][N], int n) {
  queue<int> qi;  //Две очереди с координатами, соседей которых будет проверять алгоритм
  queue<int> qj;
  qi.push(start_y);
  qj.push(start_x);
  int newx = -1, newy = -1;
  int x = 0, y = 0;
  bool used[N][N] = {{false}}; //Массив для точек, в которых побывал конь
  used[start_y][start_x] = true;
  pathX[start_y][start_x] = -2;
  pathX[start_y][start_x] = -2;
  while (!qi.empty() && !qj.empty()) {
    y = qi.front();
    x = qj.front();
    qj.pop();
    qi.pop();
    for (int i = 0; i < 8; ++i) {
      if ((x + neij[i] <= n && x + neij[i] >= 0) && (y + neii[i] <= n && y + neii[i] >= 0) && (!used[y+neii[i]][x+neij[i]])) {
        //int tmp = qi.size();
        //out << qi.size() << ' ' << qj.size() << endl;
        newx = x + neij[i];
        newy = y + neii[i];
        qj.push(newx);
        qi.push(newy);
        used[newy][newx] = true;
        if (pathX[newy][newx] == -1 && pathY[newy][newx] == -1) {
          pathX[newy][newx] = x;
          pathY[newy][newx] = y;
        }
      }
      if (newx == finish_x && newy == finish_y) {
        /*out << qj.back() << " " << qi.back() << endl;
        for (int i = 0; i < N; i++) {
          for (int j = 0; j < N; j++) {
            out << pathX[i][j] + 1 << ' ';
          } out << endl;
        }
        out << "---------------------------------------" << endl;
        for (int i = 0; i < N; i++) {
          for (int j = 0; j < N; j++) {
            out << pathY[i][j] + 1 << ' ';
          } out << endl;
        }*/
        return;
      }
    }
  }
}
 
void pathRestore(int pathX[][N], int pathY[][N], int start_x, int start_y, int finish_x, int finish_y) {
  int x = finish_x, y = finish_y;
  int newx = 0, newy = 0;
  vector< vector<int> > coord(2);
  while (x != start_y || y != start_x) {
    coord[0].push_back(x + 1);
    coord[1].push_back(y + 1);
    newx = pathX[y][x];
    newy = pathY[y][x];
    x = newx;
    y = newy;
 
  }
  coord[0].push_back(x + 1);
  coord[1].push_back(y + 1);
  out << coord[0].size() - 1 << endl;
  for (int i = coord[0].size() - 1; i != -1; i--) {
    out << coord[0][i] << ' ' << coord[1][i];
    out << endl;
  }
 
}
 
int main() {
  int n;
  in >> n;
  --n;
  int start_x, start_y;
  int finish_x, finish_y;
  in >> start_x >> start_y >> finish_x >> finish_y;
  --start_x; --start_y; --finish_x; --finish_y;
  int pathX[N][N] = {}; //Запись пути, координата Х
  int pathY[N][N] = {}; // Запись пути, координата Y
  fill(&pathX[0][0], &pathX[0][0] + N * N, -1);
  fill(&pathY[0][0], &pathY[0][0] + N * N, -1);
  horseStep(start_x, start_y, finish_x, finish_y, pathX, pathY, n);
  pathRestore(pathX, pathY, start_x, start_y, finish_x, finish_y);
 
  return 0;
}
Почему проверка на вылет за пределы доски использует нестрогое сравнение на <= n?
0
 Аватар для SaynorPRO
11 / 11 / 5
Регистрация: 05.10.2016
Сообщений: 122
10.02.2017, 21:18  [ТС]
TheCalligrapher,

из-за того, что в условии продолжения цикла почему-то x сравнивается cо start_y, а y со start_x. Что это за мешанина?
Да, тут мне и самому непонятно.

Не понимаю, зачем вам сдалась эта функция, если проблема не в ней, ну да ладно.

Изменил строчки 23, 24 и чуток переделал pathRestore. Теперь функция pathRestore здесь точно такая же, как и в рабочей программе, без встроенных очередей.

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
#include <fstream>
#include <queue>
#include <vector>
 
using namespace std;
 
ifstream in ("input.txt");
ofstream out ("output.txt");
 
const int N = 20;
const int neii[] = {2, 2, -2, -2, 1, -1, -1, 1};
const int neij[] = {-1, 1, -1, 1, -2, -2, 2, 2};
 
void horseStep(int start_x, int start_y, int finish_x, int finish_y, int pathX[][N], int pathY[][N], int n) {
  queue<int> qi;  //Две очереди с координатами, соседей которых будет проверять алгоритм
  queue<int> qj;
  qi.push(start_y);
  qj.push(start_x);
  int newx = -1, newy = -1;
  int x = 0, y = 0;
  bool used[N][N] = {{false}}; //Массив для точек, в которых побывал конь
  used[start_y][start_x] = true;
  pathX[start_y][start_x] = -2;
  pathX[start_y][start_x] = -2;
  while (!qi.empty() && !qj.empty()) {
    y = qi.front();
    x = qj.front();
    qj.pop();
    qi.pop();
    for (int i = 0; i < 8; ++i) {
      if ((x + neij[i] <= n && x + neij[i] >= 0) && (y + neii[i] <= n && y + neii[i] >= 0) && (!used[y+neii[i]][x+neij[i]])) {
        //int tmp = qi.size();
        //out << qi.size() << ' ' << qj.size() << endl;
        newx = x + neij[i];
        newy = y + neii[i];
        qj.push(newx);
        qi.push(newy);
        used[newy][newx] = true;
        if (pathX[newy][newx] == -1 && pathY[newy][newx] == -1) {
          pathX[newy][newx] = x;
          pathY[newy][newx] = y;
        }
      }
      if (newx == finish_x && newy == finish_y) {
        /*out << qj.back() << " " << qi.back() << endl;
        for (int i = 0; i < N; i++) {
          for (int j = 0; j < N; j++) {
            out << pathX[i][j] + 1 << ' ';
          } out << endl;
        }
        out << "---------------------------------------" << endl;
        for (int i = 0; i < N; i++) {
          for (int j = 0; j < N; j++) {
            out << pathY[i][j] + 1 << ' ';
          } out << endl;
        }*/
        return;
      }
    }
  }
}
 
void pathRestore(int pathX[][N], int pathY[][N], int start_x, int start_y, int finish_x, int finish_y) {
  int x = finish_x, y = finish_y;
  int newx = 0, newy = 0;
  vector< vector<int> > coord(2);
  while (x != -2) {
    coord[0].push_back(x + 1);
    coord[1].push_back(y + 1);
    newx = pathX[y][x];
    newy = pathY[y][x];
    x = newx;
    y = newy;
 
  }
  if (x > -1 && y > -1) {
    coord[0].push_back(x + 1);
    coord[1].push_back(y + 1);
  }
  out << coord[0].size() - 1 << endl;
  for (int i = coord[0].size() - 1; i != -1; i--) {
    out << coord[0][i] << ' ' << coord[1][i];
    out << endl;
  }
 
}
 
int main() {
  int n;
  in >> n;
  --n;
  int start_x, start_y;
  int finish_x, finish_y;
  in >> start_x >> start_y >> finish_x >> finish_y;
  --start_x; --start_y; --finish_x; --finish_y;
  int pathX[N][N] = {}; //Запись пути, координата Х
  int pathY[N][N] = {}; // Запись пути, координата Y
  fill(&pathX[0][0], &pathX[0][0] + N * N, -1);
  fill(&pathY[0][0], &pathY[0][0] + N * N, -1);
  horseStep(start_x, start_y, finish_x, finish_y, pathX, pathY, n);
  pathRestore(pathX, pathY, start_x, start_y, finish_x, finish_y);
 
  return 0;
}
Теперь не вылетает(ваш пример)
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13241 / 6873 / 1827
Регистрация: 18.10.2014
Сообщений: 17,422
10.02.2017, 21:46
Лучший ответ Сообщение было отмечено SaynorPRO как решение

Решение

Цитата Сообщение от SaynorPRO Посмотреть сообщение
если проблема не в ней
Что значит "проблема не в ней"? Я запускаю вашу программу и она вылетает в pathRestore из-за явной ошибки в pathRestore. О каком "проблема не в ней" может идти речь?

Проблем разного рода в вашем коде много.

Цитата Сообщение от SaynorPRO Посмотреть сообщение
Теперь не вылетает(ваш пример)
Теперь, вроде, все работает. Код ужасен, но вылетов я не наблюдаю.

----

В horseStep к чему вот это вот

C++
1
2
  pathX[start_y][start_x] = -2;
  pathX[start_y][start_x] = -2;
Во второй строчке, очевидно, имелся в виду pathY. На работоспособность это "не влияет", ибо pathRestore проверяет только x, но все же дичь налицо.

----

В horseStep что вот это за странная проверка

C++
1
        if (pathX[newy][newx] == -1 && pathY[newy][newx] == -1) {
Что именно она проверяет и зачем?

Роль этой проверки уже взял на себя массив used. Либо продолжайте пользоваться used, тогда эта проверка ни нафиг не нужна, ибо условие будет всегда истинно. Либо выкиньте нафиг совершенно ненужный массив used и используйте вместо него pathX и/или pathY.

----

В pathRestore за циклом

C++
1
2
3
while (x != -2) {
  ...
}
следует проверка

C++
1
2
3
4
if (x > -1 && y > -1) {
    coord[0].push_back(x + 1);
    coord[1].push_back(y + 1);
}
Это как это такое может быть, если цикл заведомо завершается с x == -2?

Добавлено через 6 минут
Цитата Сообщение от SaynorPRO Посмотреть сообщение
Я n уменьшаю, если что, в начале программы
Возникает вопрос - зачем??? То, что вы уменьшаете координаты на 1 в "в начале программы" - это понятно, это переход от индексации с 1 к индексации с 0.

А n-то зачем было уменьшать? n - это размер. Его нет никаких причин вдруг уменьшать. Разве что только запутать читателя кода (меня - успешно запутали).
2
 Аватар для SaynorPRO
11 / 11 / 5
Регистрация: 05.10.2016
Сообщений: 122
10.02.2017, 22:06  [ТС]
TheCalligrapher, сейчас всё объясню.

Проблем разного рода в вашем коде много
Для решения их я и написал на этот форум.

Код ужасен
Код написан для решения задачи на графы, в которой используется координатная плоскость(шахматная доска). Соответственно, я должен в голове держать вид этой доски в координатной плоскости и вид этой доски в массиве, не думаю, что вы нуждаетесь в объяснении их различий. И использовать я должен одновременно эти два вида в программе, т.е. при работе с соседями - вид массива, при выводе - вид координатной плоскости, т.к. этого требует условие. Надеюсь я объяснил, почему так просто запутаться в этом коде.

К чему вот это вот
В функции pathRestore я иду с конечной вершины, до начальной. Поэтому я просто пометил начальную вершину в массиве предков как -2. То есть, как только функция pathRestore, дойдёт до начальной вершины, переменные x и y получат значения -2(-2, потому что он изначально заполнен у меня как -1, -1 означает, что к клетке нету пути, я это проверяю в функции horseStep. Предрекаю вопрос "почему не ноль?". Ответ: ноль может быть координатой)
, выполнится проверка условия и произойдёт выход из цикла.

На работоспособность это "не влияет", ибо pathRestore проверяет только x, но все дичь налицо.
Проверяет, только x, потому что у y будет такое же значение, так что разницы нету. Можете приписать && y != -2, разницы не будет. А можете вообще поменять проверку на y != -2, всё будет так же.


Надеюсь всё понятно объяснил. На данный момент у меня появились новые проблемы. Вылетов с bad_alloc больше нет, но ответ программа выдаёт все равно неправильный. И тут у меня даже мыслей нету, как это можно исправить, потому что в версии программы с ручными очередями, всё то же самое, просто заменены очереди. Там всё работает идеально. Как я сказал ранее, по факту я заменил только очереди. Неужели я как-то криво обрабатываю встроенные очереди? Если хотите, я могу скинуть код рабочей версии программы, чтобы вы убедились в моих словах.

Кстати, условие в строке 76 можно убрать, оно не нужно, я проверил.

Добавлено через 8 минут
TheCalligrapher,

Роль этой проверки уже взял на себя массив used. Либо продолжайте пользоваться used, тогда эта проверка ни нафиг не нужна, ибо условие будет всегда истинно. Либо выкиньте нафиг совершенно ненужный массив used и используйте вместо него pathX и/или pathY.
Спасибо, вы правы, всё так. Исправил.

C++
1
if ((x + neij[i] <= n && x + neij[i] >= 0) && (y + neii[i] <= n && y + neii[i] >= 0) && ((pathX[y+neii[i]][x+neij[i]] == -1) && (pathY[y+neii[i]][x+neij[i]] == -1)))
А n-то зачем было уменьшать? n - это размер. Его нет никаких причин вдруг уменьшать. Разве что только запутать читателя кода (меня - успешно запутали).
Ну, раз мы работаем в индексации, начинающейся с 0, значит и размер нужно уменьшить. Наоборот, мне кажется, чтобы никто не запутался, нужно все значения конвертировать.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13241 / 6873 / 1827
Регистрация: 18.10.2014
Сообщений: 17,422
10.02.2017, 22:46
Лучший ответ Сообщение было отмечено SaynorPRO как решение

Решение

Цитата Сообщение от SaynorPRO Посмотреть сообщение
В функции pathRestore я иду с конечной вершины, до начальной
Я прекрасно знаю, какую роль массивы pathX и pathY играют в вашем алгоритме. Речь идет лишь о том, что в ваше коде содержится бессмысленное двойное присваивание

C++
1
2
  pathX[start_y][start_x] = -2;
  pathX[start_y][start_x] = -2;
одного и того же значения в одно и то же место.

Если проследить эволюцию этого места в вашем коде, то очевидно, что вы уже обращали на это место внимание. Но разглядеть ляп все равно не смогли. Это, кстати, лишний повод упомянуть, что вместо того, чтобы плодить независимые массивы pathX и pathY для X и Y надо было не полениться, а завести структуру - пару { x, y } - и хранить ее уже в одном-единственном массиве path.

Цитата Сообщение от SaynorPRO Посмотреть сообщение
-1 означает, что к клетке нету пути, я это проверяю в функции horseStep. Предрекаю вопрос "почему не ноль?". Ответ: ноль может быть координатой)
Как я уже сказал выше, в присутствии массива used проверка pathX и pathY на -1 в функции horseStep - совершенно бессмысленна. Эта проверка всегда истинна, ибо проверку на "уже посещенность" клетки у вас возложена на массив used. До тех пор, пока эта задача возложена на массив used, никакого смысла в инициализации ваших массивов pathX и pathY значением -1 нет и никакого смысла в проверке на -1 тоже нет. Вы можете вообще изначально не инициализировать pathX и pathY - оставить там мусор - и убрать из кода ненужную проверку на -1. На работоспособность программы это не повлияет.

Либо выкиньте массив used вообще, а проверку посещенности клетки делайте через pathX и pathY. Тогда изначальная инициализация -1, разумеется, нужна. (Я так понимаю, что вы уже так и сделали.)

Цитата Сообщение от SaynorPRO Посмотреть сообщение
Ну, раз мы работаем в индексации, начинающейся с 0, значит и размер нужно уменьшить. Наоборот, мне кажется, чтобы никто не запутался, нужно все значения конвертировать.
Это как это? В языках С и С++ мы привыкли к индексации с 0. То есть при размере массива N допустимыми являются индексы от 0 до N-1. То есть размер всегда на 1 больше, чем максимально допустимый индекс. И проверка на попадание в диапазон допустимых индексов выглядит как 0 <= i && i < N. Обратите внимание на строгое сравнение во втором случае.

Это то, к чему мы привыкли в С++. Так было всегда.

Поэтому при переходе от индексации с 1 к индексации с 0 из индексов вычитается 1, но из размера ничего никогда вычитать не надо.

Вы же вычли из размера 1, и проверка на правильность индекса у вас приобрела вид 0 <= i && i <= N. Это вызывает справедливое недоумение: зачем из размера вычли 1? Если размер доски 8, то он и в Африке 8, независимо от выбранного способа индексации. Почему вдруг в N оказалось 7?

Кому-то, возможно, в такой ситуации больше нравится работать не с размером, а с максимальным индексом. Тогда все становится на свои места - действительно из максимального индекса надо вычесть 1, и действительно проверка на попадание в диапазон будет выглядеть как 0 <= i && i <= max. Но тогда лучше не называть его n, а назвать его, например, max_i или еще что-то в этом роде. А n - скорее имя для размера, а не для индекса.
1
 Аватар для SaynorPRO
11 / 11 / 5
Регистрация: 05.10.2016
Сообщений: 122
10.02.2017, 23:43  [ТС]
TheCalligrapher,

Если размер доски 8, то он и в Африке 8, независимо от выбранного способа индексации
Хорошо, теперь буду делать всегда как вы сказали.

ваше коде содержится бессмысленное двойное присваивание
Моя вина. Во второй строчке не pathX, а pathY.

Что же в итоге. Я случайно переделал очередь не в очередь, а в стек. Самое интересное, что он вроде как выдаёт адвекватный ответ(как оказалось - не совсем, до клетки он доходит, но путь - не кратчайший). Я допускаю ужасные ошибки - я знаю. Но я программирую чуть больше полугода, а на плюсах - хорошо если месяц будет, хотя то что я не заметил в упор, что сделал это бессмысленное присваивание - это не зависит от опыта программирования, тут моя рассеянность сыграла роль.

Однако, в конце концов, я исправил все недочёты и теперь могу с уверенностью сказать, что программа на 100% работоспособная(чекер полностью засчитал). Корень проблемы оказался не в функции horseStep, а в pathRestore. Скорее всего, из-за своей уверенности в том, что ошибка в horseStep(уже не помню, на основе чего я вынес это решение), я даже и мысли не допускал, что может быть по другому.

Огромное спасибо всем, кто ковырялся в моём коде и пытался помочь. В частности спасибо TheCalligrapher и likehood, за проявленное внимание к чужой проблеме.

Полностью работоспособный код
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
#include <fstream>
#include <queue>
#include <vector>
 
using namespace std;
 
ifstream in ("input.txt");
ofstream out ("output.txt");
 
const int N = 20;
const int neii[] = {2, 2, -2, -2, 1, -1, -1, 1};
const int neij[] = {-1, 1, -1, 1, -2, -2, 2, 2};
 
void horseStep(int start_x, int start_y, int finish_x, int finish_y, int pathX[][N], int pathY[][N], int n) {
  queue<int> qi;  //Две очереди с координатами, соседей которых будет проверять алгоритм
  queue<int> qj;
  qi.push(start_y);
  qj.push(start_x);
  int newx = -1, newy = -1;
  int x = 0, y = 0;
  pathX[start_y][start_x] = -2;
  pathX[start_y][start_x] = -2;
  while (!qi.empty() && !qj.empty()) {
    y = qi.front();
    x = qj.front();
    qj.pop();
    qi.pop();
    for (int i = 0; i < 8; ++i) {
      if ((x + neij[i] <= n && x + neij[i] >= 0) && (y + neii[i] <= n && y + neii[i] >= 0) && ((pathX[y+neii[i]][x+neij[i]] == -1) && (pathY[y+neii[i]][x+neij[i]] == -1))) {
        newx = x + neij[i];
        newy = y + neii[i];
        qj.push(newx);
        qi.push(newy);
        pathX[newy][newx] = x;
        pathY[newy][newx] = y;
      }
      if (newx == finish_x && newy == finish_y) {
        return;
      }
    }
  }
}
 
void pathRestore(int pathX[][N], int pathY[][N], int start_x, int start_y, int finish_x, int finish_y) {
  int x = finish_x, y = finish_y;
  int newx = 0, newy = 0;
  vector< vector<int> > coord(2);
  while (x != -2) {
    coord[0].push_back(x + 1);
    coord[1].push_back(y + 1);
    newx = pathX[y][x];
    newy = pathY[y][x];
    x = newx;
    y = newy;
 
  }
  out << coord[0].size() - 1 << endl;
  for (int i = coord[0].size() - 1; i != -1; i--) {
    out << coord[0][i] << ' ' << coord[1][i];
    out << endl;
  }
 
}
 
int main() {
  int n;
  in >> n;
  --n;
  int start_x, start_y;
  int finish_x, finish_y;
  in >> start_x >> start_y >> finish_x >> finish_y;
  --start_x; --start_y; --finish_x; --finish_y;
  int pathX[N][N] = {}; //Запись пути, координата Х
  int pathY[N][N] = {}; // Запись пути, координата Y
  fill(&pathX[0][0], &pathX[0][0] + N * N, -1);
  fill(&pathY[0][0], &pathY[0][0] + N * N, -1);
  horseStep(start_x, start_y, finish_x, finish_y, pathX, pathY, n);
  pathRestore(pathX, pathY, start_x, start_y, finish_x, finish_y);
  return 0;
}
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13241 / 6873 / 1827
Регистрация: 18.10.2014
Сообщений: 17,422
11.02.2017, 00:07
Цитата Сообщение от SaynorPRO Посмотреть сообщение
Что же в итоге. Я случайно переделал очередь не в очередь, а в стек. Самое интересное, что он вроде как выдаёт адвекватный ответ(как оказалось - не совсем, до клетки он доходит, но путь - не кратчайший).
Вся идея такого алгоритма поиска кратчайшего пути основана на применении поиска в ширину, т.е. на принципе моделирования поведения волны, расходящейся равномерно во все стороны от стартовой точки до тех пор, пока эта волна не коснется искомой конечной точки. Если волна расходилась во все стороны равномерно, то она достигнет конечной точки по кратчайшему пути. В данном случае волна у нас не совсем обычная - прыгающая - но на сам принцип это не влияет.

И чтобы этот принцип работал правильно, т.е. чтобы волна расходилась от стартовой точки равномерно во все стороны, нам необходимо придерживаться следующего правила: чем раньше волна достигла некоей точки, тем раньше она должна пройти через эту точку дальше. Именно это обуславливает необходимость использования именно очереди (FIFO), а не стека (LIFO) и именно это дает нам "поиск в ширину".

Если заменить очередь стеком, то мы получим алгоритм псевдо-"поиска в глубину". Этот алгоритм будет находить какой-то путь от старта к финишу, но совершенно не обязательно кратчайший.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
11.02.2017, 00:07

Ошибка terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc
При выполнении программы, которая миксует функции в которых создаются типовые задачи, вылезает ошибка, в чем проблема?? #include...

Ошибка std::bad_alloc
Добрый день, возникает ошибка std::bad_alloc когда вызывается функция void new_error(string error_text) у класса который ниже //Класс...

Ошибка std::bad_alloc
Здравствуйте! Уже который день борюсь с этой ошибкой, но не могу понять, в чем проблема. После возникновения ошибки ругается на...

Ошибка std::bad_alloc
Помогите. Если запускать программу с number = 6, то всё работает, а вот если запустить программу, поменяв 6 на любое другое число, то...

Ошибка: terminate called after throwing an instance of 'std::bad_alloc'
Доброго времени суток В сурсе #include &lt;iostream&gt; #include &lt;fstream&gt; #include &lt;vector&gt; #include &lt;array&gt; #include...


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

Или воспользуйтесь поиском по форуму:
34
Ответ Создать тему
Новые блоги и статьи
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой. Но использовать несколько программ не удобно. Искал другие. . .
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской) Options Preferences General Language
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru