Post #195

Как быстро найти ближайший красный/черный пиксель? Представим что нас устраивает более простая - Манхэттоновская метрика: |x₁-x₂| + |y₁-y₂|. Т.е. нас интересует кратчайшее расстояние измеряемое в горизонтальных + вертикальных смещениях (т.е. шаг по диагонали = расстояние 2). Это можно посчитать за O(w*h) стандартным методом динамического программирования: init: d[y][x] = 0, если pixel[y][x] — красный пиксель d[y][x] = ∞ иначе forward pass: d[y][x] = min(d[y][x], d[y][x-1]+1, d[y-1][x]+1) backward pass: d[y][x] = min(d[y][x], d[y][x+1]+1, d[y+1][x]+1)