Как исправить ошибку Memory limit?

Question

[Viva8888]

Тут мое решение https://pastebin.com/bWksj4KK

Буду признателен, если поможете. Готов ответить на любые вопросы по решению и условию

Answer 1

[jcmvbkbc]

Подозреваю, что дело в локальных переменных i и j в строках 42 и 43 и использовании какого-нибудь старого стандарта C++ продлевающего их области действия до конца охватывающего блока, из-за чего в check не отрабатывает условие в строке 30. Предлагаю убрать int в строках 42 и 43.

Comments

[Viva8888]

Исправил, получился такой код https://pastebin.com/wsX5NtAw. Опять падает на том же самом тесте с ML.
Ограничение по памяти 64 мб, dроде должна была зайти)

[jcmvbkbc]

Да, ещё
if(res[ii][jj] < res[i][j])
в строке 28 имеет смысл заменить на
if(res[ii][jj] <= res[i][j] + 1)

Answer 2

[Wataru]

Ошибка в функции check. Вам тогда надо проверять, что текущее расстояние до ii, jj меньше или равно расстояния до i,j +1. Чтобы вы возвращали 0, если нет смысла переписывать расстояние и добавлять вершину в очередь.

Из-за этого у вас каждая вершина может быть в очереди кучу раз.

Вообще, по уму, надо бы завести массив bool пометок и их использовать чтобы помечать, а бала ли вершина в очереди уже. И проверять в check эти пометки вместо неявной логики на основе расстояния. Плюс у вас там используются глобальные i, j, что делает чтение этой функции очень неудобным. Такая неявная передача параметров - очень плохая идея.