Программа вылетает с ошибкой std::bad_alloc

[SaynorPRO]

#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] = 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) {
      bool beyondCheckX = (x + neij[i] <= n && x + neij[i] >= 0); //проверка выхода за пределы массива
      bool beyondCheckY = (y + neii[i] <= n && y + neii[i] >= 0);
      bool usedCheck = (!used[y+neii[i]][x+neij[i]]);
      if (beyondCheckX && beyondCheckY && usedCheck) {
        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 15 14 7 8 она вылетает, а при вводе 20 5 5 1 1 всё хорошо.

• Программа вылетает в функции horseStep

Главный вопрос - почему она так безбожно жрёт память? Не рекурсий, ничего, при дебаге, максимальный размер очереди был равен 81, далее она начинает потихоньку уменьшаться. Кстати говоря, программа вылетает всего при 57 элементах в очереди(в общем 114 элементов, т.к. очереди у меня две). ВСЁ. Больше эта функция ничего не создаёт, она просто работает с уже имеющимися значениями, память для которых уже существует(пара небольших массивов и переменных). Так почему она всё выделяет и выделяет память?

Скриншот ошибки, если надо: Безымянный.jpg

[SaynorPRO]

Задача решена.

#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;
}