НОВ БЪЛГАРСКИ УНИВЕРСИТЕТ

Департамент Информатика

XVIIІ РЕПУБЛИКАНСКА СТУДЕНТСКА ОЛИМПИАДА ПО ПРОГРАМИРАНЕ

13 - 14 май 2006 г.

---

Задача I. Хаусдорфово разстояние

Хаусдорфово разстояние h между две непразни множества A и B в метрично пространство се дефинира по следния начин:

 h(A,B) = max{max_{a \in A}min_{b \in B}\rho(a, b), max_{b \in B}min_{a \in A}\rho(b, a)}, 

където с \rho(a, b) е означено разстояние (в метриката на пространството) между точките a \in A и b \in B. Нека метричното пространство е равнината и разстоянието между точките измерваме с "квадратна" норма, т.е. \rho(a,b) = max{|a_1 - b_1|, |a_2 - b_2|}, където a = (a_1, a_2) и b = (b_1, b_2).
Ще разглеждаме множества, които се съдържат в даден правоъгълник със страни успоредни на координатните оси. Множествата са дискретни, т.е. можем да предполагаме, че се състоят от цветни точки (пиксели), като останалата част от правоъгълника се състои от бели пиксели. Например, нека множеството A е образувано от червени пиксели, а множеството B - от сини. Тогава в правоъгълника P, съдържащ множествата, ще се има най-много 4 цвята - червен за A\B, син за B\A, зелен за A \cap B и бял за P \ (A \cup B). Ако в P има само зелено и бяло, то A = B и h(A, B) = 0. Ако има червено, зелено и бяло (няма синьо), то B \subset A и h(A,B) = max_{a \in A}min_{b \in B}\rho(a, b), защото max_{b \in B}min_{a \in A} \rho(b, a) = 0.
Да се напише програма I, която намира хаусдорфовото разстояние между две дадени множества в равнината.
Тази задача възниква при търсене на текст (дума) в точкови изображения (bitmap images) - например сканиран документ. Тогава всяка отделена (сегментирана) дума от изображенията се сравнява с даден шаблон. Ефективността на алгоритъма е от съществено значение, защото той трябва да се изпълнява много пъти - например 50 страници стандартен машинописен текст съдържат 10-15 хил. думи.

Вход
Първият ред на всеки пример съдържа две цели положителни числа m и n -- размерността на матриците (1 < m, n < 1000), представящи двете множества, като един пиксел от правоъгълника съответства на един елемент от матрицата. Следват елементите на двете матрици по редове. Те задават характеристичните функции на множествата, т.е. 1 означава точка от множеството (цветен пиксел). Входът съдържа много примери и завършва с 0 0.

Изход
На стандартния изход на отделни редове се записват намерените разстояния за примерите от входа.
Примерен вход:
3 3
1 1 1
0 0 0
0 0 0
1 1 1
1 0 0
0 0 0
3 4
1 1 1 0
0 0 0 0
0 0 0 0
1 1 0 1
0 0 0 1
1 0 0 0
0 0

Изход -- решение за примерния вход:
1
2