Можно же изменять только крайние цифры по услолвию. Поэтому может быть нужно сделать до 7 поворотов.
Тут, наврено, даже можно разобрать кучу случаев и придумать какую-то стратегию, но это явно задача на обход в ширину (судя по прошлым задачам от автора - это какой-то курс и они сейчас bfs проходят).
impelix, вы dist храните в КЛЮЧЕ мапа. Вы dist игнорируете в операторе сравнения и две ошибки какбы компенсируют друг друга, но это концептуально - бред. Вам надо мап из координат в int- расстояние и пару координат.
impelix, не совсем поавильно. Надо чтобы dist хранился в map, а не был частью ключа. Вместо проверки на visited, можно смотреть, что по заданным координатам в map что-то лежит. Если нет - положить туда +1 к тому, что лежит по координатам из очереди.
Это часть какой-то задачи. Давайте исходную задачу, потому что эту часть особо не наоптимизируешь. Все равно придется по всем клеткам пройтись, чтобы найти там t.
Ну, хранить квадрат расстояния и не использовать pow чтобы счет в целых числах шел, ускорит в пару раз, но не принципиально.
mayton2019, да, так можно сделать, конечно, но в этой задаче это не надо. И вы замучаетесь разбирать случаи. Например кони в А1 и B2. Вот там из-за границы поля нифига не один ход. Потом, если кони далеко, но у границы поля - это тоже надо аккуратно разбирать.
impelix, Давайте новый код. У вас где-то другая ошибка. Alexandroppolus все правильно сказал. Вот только я согласен с вами, что совпадение проверять не обязательно. Просто там bfs найдет 0 и это ответ.
mayton2019, 1000x1000 для bfs - фигня. Ну, можно A* запустить - тогда и хитрость с жадным хождением в сторону второго коня пока они далеко, автоматически воспроизведется.
impelix, Ошибки в коде вашем я не вижу. Возможно оно все такие тесты как раз и проходит. Но на тесте, где кони на разных цветах стоят, оно выдает неправильный ответ.
Alexandroppolus, Вы абсолютно правы, но в задаче же не дано, что они на полях одного цвета. И решать этот частный случай смысла никакого нет - только кода в 2 раза больше. Ведь ограничения по времени в таких задачах обычно всегда отдельно по тестам и ускорение в каких-то не самых тяжелых тестах ничем не поможет.
Akina, если путь нечетной длины - то не все так просто. На самом деле тут слишком маленькие числа, чтобы надо было какую-то хитрость придумывать. Досаточно bfs в пространстве состояний (4 координаты).
std::vector<int>- это класс, который хранит массив int в c++.