Qatlanmış xəritə
Fredin bağı o qədər böyükdür ki, hansı tərəvəzlərin hansı sahədə əkildiyini göstərən bir xəritəyə ehtiyacı var. O, Beynəlxalq Kartoqrafiya Şirkətindən yüksək keyfiyyətli bir xəritə sifariş etdi. Xəritə böyük miqyasda olduğuna görə bir səhifəyə yerləşmir və buna görə də bir neçə düzbucaqlı hissəyə bölünməlidir.
Hissənin ölçüsü (səhifənin ölçüsü ilə müəyyən edilir) və xəritənin miqyası sabit olsa da, xəritənin hissələrinin sayı şəbəkənin yerləşdirilməsindən asılı olaraq dəyişə bilər. Sizdən Fredin bağı üçün bütün ərazini əhatə etmək üçün lazım olan minimal xəritə hissələrinin sayını tapmaq tələb olunur.
Texas bölgəsinin yerləşdirilməsi üçün bir çox variantdan ikisi:
Gəlin bir nümunəyə baxaq. Solda bölgəni əhatə edən 14 xəritə hissəsi göstərilib. Lakin xəritənin mövqeyini bir az dəyişdirsək, eyni bölgəni ölçü və istiqaməti dəyişmədən cəmi 10 hissə ilə əhatə etmək olar.
Bütün xəritə hissələri x və y oxlarına paralel düzbucaqlı bir şəbəkəyə aid olmalıdır. Yəni onlar yalnız tam tərəflərlə toxuna bilər və döndərilə bilməzlər.
Giriş məlumatları
Bir neçə testdən ibarətdir. Hər testin ilk sətiri dörd tam ədədi ehtiva edir: A[r], A[c], T[r] və T[c]. A[r] və A[c] giriş təsvirinin piksel olaraq icazəsini təyin edir (1 ≤ A[x] ≤ 1000), T[r] və T[c] isə xəritənin bir hissəsinin piksel olaraq ölçüsünü təyin edir (1 ≤ T[x] ≤ 100). Növbəti A[r] sətirin hər biri A[c] simvolu ehtiva edir, hər biri ya "X" (xəritə hissəsi ilə əhatə olunmalı olan bağın bir hissəsinə uyğun gələn piksel) və ya "." (əhatə olunmamalı olan bağdan kənar piksel). Bölgənin nöqtələri birləşmiş bir sahə təşkil edir.
Çıxış məlumatları
Hər test üçün bütün "X" tipli pikselləri əhatə edə biləcək minimal xəritə hissələrinin sayını ayrı bir sətirdə çıxarın.