Есть квадратная сетка размера N * N, в каждой клетке которой записано магическое целое положительное число. Дистанция между двумя клетками равна сумме магических чисел в этих клетках и Евклидову расстоянию между этими клетками. Среди всех этих клеток R клеток покрашены в красный цвет, а G клеток покрашены в зеленый цвет. Для каждой зеленой клетки нужно найти такую красную, что не будет другой красной клетки дистанция до которой меньше.
512 <= N <= 4096
1 <= R + G <= N * N
Можно ли решить эту задачу быстрее чем O(G * R)? Если бы не было магического числа в клетках, то это была бы задача по поиску ближайшего соседа.
Auto comment: topic has been updated by xagofes (previous revision, new revision, compare).
Ну, во-первых, откуда задача эта?
Во-вторых, как даже за O(G * R) это решается?
upd: а лол, не так прочитал условие, хватит минусовать меня, я не настолько тупой((((((((
It seems like some structures for finding the nearest neighbor allow using custom metrics to calculate the distance. For example, Ball tree .
Простое дп в четыре стороны (минимальная по значению + расстоянию красная слева сверху, справа сверху, слева снизу, справа снизу), пересчет несложный. Получается O(N2).
Unless I'm misunderstanding the problem, a simple BFS should be sufficient, finding the shortest path on an unweighted graph from multiple sources. Run BFS using every red cell as a source. To account for the "magic numbers", only add each red cell to the queue once the smallest distance currently in the queue equals its "magic number". Runs in O(N*N) which appears to be the expected running time for N <= 4096.
In this problem distance between two sells is equal to Euclidean distance ( + smth). not Manhattan distance. So usual BFS does not work
Ah, you're right, I was thinking of Manhattan distance.