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