Это часть какой-то задачи. Давайте исходную задачу, потому что эту часть особо не наоптимизируешь. Все равно придется по всем клеткам пройтись, чтобы найти там t.
Ну, хранить квадрат расстояния и не использовать pow чтобы счет в целых числах шел, ускорит в пару раз, но не принципиально.
mayton2019, да, так можно сделать, конечно, но в этой задаче это не надо. И вы замучаетесь разбирать случаи. Например кони в А1 и B2. Вот там из-за границы поля нифига не один ход. Потом, если кони далеко, но у границы поля - это тоже надо аккуратно разбирать.
impelix, Давайте новый код. У вас где-то другая ошибка. Alexandroppolus все правильно сказал. Вот только я согласен с вами, что совпадение проверять не обязательно. Просто там bfs найдет 0 и это ответ.
mayton2019, 1000x1000 для bfs - фигня. Ну, можно A* запустить - тогда и хитрость с жадным хождением в сторону второго коня пока они далеко, автоматически воспроизведется.
impelix, Ошибки в коде вашем я не вижу. Возможно оно все такие тесты как раз и проходит. Но на тесте, где кони на разных цветах стоят, оно выдает неправильный ответ.
Alexandroppolus, Вы абсолютно правы, но в задаче же не дано, что они на полях одного цвета. И решать этот частный случай смысла никакого нет - только кода в 2 раза больше. Ведь ограничения по времени в таких задачах обычно всегда отдельно по тестам и ускорение в каких-то не самых тяжелых тестах ничем не поможет.
Akina, если путь нечетной длины - то не все так просто. На самом деле тут слишком маленькие числа, чтобы надо было какую-то хитрость придумывать. Досаточно bfs в пространстве состояний (4 координаты).
Тут 0 - корень дерева. Почему он не подходит? Если приложить второое дерево к корню, то все вершины совпадут, только некоторые не будут листами. Т.е. вам надо именно по листьям прикладывать? Тогда на мой предыдущий вопрос ответ будет не "все поддеревья, у которых есть левый ребёнок", а все "все поддеревья, у которых есть левый ребёнок и он - лист". Так что же вам надо?
gasonger0, Т.е - те места, куда можно "приложить" второе дерево. Деревья могут быть любыми? А то у вас ввод как-то странно сделан. Не похоже что там вообще что-то кроме полных деревьев определенного уровня можно вводить.
gasonger0, Вот, например, второе дерево это корень и один левый ребенок. Вам в ответ надо вывести все вершины первого дерева, у которых есть левый ребенок, или все вершины, у которых левый ребенок - лист?
В коде вижу какие-то lvl_a, cur_lvl_b - Это типа оптимизация?
Ну, хранить квадрат расстояния и не использовать pow чтобы счет в целых числах шел, ускорит в пару раз, но не принципиально.