Структура сетки 2D-сетки для ближайшей свободной ячейки

Question

Рассмотрим массив двухмерного массива 2000 x 2000. 100 000 элементов установлены в true, остальное - false.

Для ячейки (x1, y1) нам нужно найти ближайшую ячейку (x2, y2) (по манхаттанскому расстоянию: abs (x1-x2) + abs (y1-y2)), которое является ложным.

Один из способов сделать это было бы:

for (int dist = 0; true; dist++) 
    for ((x2,y2) in all cells dist away from (x1,y1)) 
     if (!array[x2,y2]) 
      return (x2,y2); 

В худшем случае нам придется перебрать 100000 клеток, прежде чем найти один свободный.

Есть ли структура данных, которую мы могли бы использовать, а не 2D-массив, который позволил бы нам быстрее выполнять этот поиск?

Answer 1

Если данные постоянны и у вас есть много запросов на него:
Возможно, вы захотите использовать k-d tree, и ищите ближайшего соседа. Вставьте (i,j) для каждого элемента, такого как arr[i][j] = false. Дерево стандарт кД использует евклидово расстояние, но я думаю, что можно изменить его использовать вместо расстояний Манхэттен ..

Если данные используются для одного запроса:
Вам нужно по крайней мере Omega(n*m) опа читать данные и вставьте его в любую структуру данных - поэтому не стоит этого делать - предлагаемое решение превзойдет только наращивание любой структуры данных.

Answer 2

Возможно, вас заинтересует Region QuadTree. Здесь изначально все изображение моделируется как корень, так как изображение содержит все 0s (предположение). Затем, когда задан определенный пиксель, изображение сначала делится на 4 квадранта, а 3 квадранта, где пиксель не включен, остаются в виде листьев. Оставшийся квадрант подразделяется снова и так далее. Это достигается до тех пор, пока у нас не будет 4 точечных листьев, из которых один будет установлен. Это представление поможет исключить целые регионы во время поиска, а время поиска можно оптимизировать до O (log n)