Patisserie ACM
Amber Claes Maes, bir patissier olaraq, keçən ay öz dükanını açdı. O, dükanını tanıtmaq məqsədilə işini Beynəlxalq Şokolad Patissier Müsabiqəsinə təqdim etməyə qərar verdi və şirin şokolad batonlarının reseptini hazırladı. Minlərlə sınaqdan sonra nəhayət resepti əldə etdi. Lakin, resept şokoladı nizamlı düzbucaqlı formaya gətirmək üçün yüksək bacarıq tələb edirdi. Təəssüf ki, o, yenicə Şəkil 1-də göstərilən qəribə formalı başqa bir şokolad batonu hazırladı.
Şəkil 1: Qəribə formalı şokolad batonu
Hər bir şokolad batonu çoxlu kiçik düzbucaqlı şokolad seqmentlərindən ibarətdir. Bitişik seqmentlər arasında onları asanlıqla qırmaq üçün bir yiv var. O, qəribə formalı şokolad batonlarını bir neçə düzbucaqlı parçalara kəsməyi və dükanında satmağı planlaşdırırdı. O, hər bir şokolad batonunu aşağıdakı kimi kəsmək istəyir:
Baton yivlər boyunca kəsilməlidir.
Baton düzbucaqlı parçalara kəsilməlidir.
Baton mümkün qədər az parçalara kəsilməlidir.
Qaydaları izləyərək, Şəkil 2 Şəkil 1-də göstərilən şokolad batonunun kəsilməsinin bir nümunəsi ola bilər. Şəkil 3 və 4 qaydalara uyğun gəlmir; Şəkil 3-də qeyri-düzbucaqlı bir parça var və Şəkil 4-də Şəkil 2-dən daha çox parça var.
Şəkil 2: Qaydaları izləyən kəsilmə nümunəsi
Şəkil 3: Qeyri-düzbucaqlı parça buraxan kəsilmə nümunəsi
Şəkil 4: Şəkil 2-dən daha çox parça verən kəsilmə nümunəsi
Sizin işiniz, qaydalara uyğun olaraq kəsildikdən sonra şokolad parçalarının sayını hesablayan bir proqram yazmaqdır.
Giriş verilənləri
Giriş bir sıra datasetlərdən ibarətdir. Girişin sonu boşluqla ayrılmış iki sıfır olan bir sətirlə göstərilir. Hər bir dataset aşağıdakı kimi formatlanır:
h wr_{(1, 1)} ... r_{(1, w)}r_{(2, 1)} ... r_{(2, w)}...r_{(h, 1)} ... r_{(h, w)}
Tam ədədlər h və w şokoladın iki ortogonal ölçüsünün uzunluqlarıdır, seqmentlərin sayında. Siz 2 ≤ h ≤ 100 və 2 ≤ w ≤ 100 olduğunu qəbul edə bilərsiniz. Aşağıdakı hər bir h sətiri w simvoldan ibarətdir, hər biri ya "." ya da "#"dir. Simvol r_{(i, j)} şokolad seqmentinin (i, j) mövqeyində olub-olmadığını aşağıdakı kimi göstərir:
".": Şokolad yoxdur.
"#": Şokolad seqmenti var.
Siz Şəkil 5-də təsvir edildiyi kimi ya çoxlu ayrılmış batonları, ya da Şəkil 6 və 7-də təsvir edildiyi kimi dəlikli bir baton təmsil edən heç bir datasetin olmadığını qəbul edə bilərsiniz. Hər bir datasetdə ən azı bir "#" simvolunun olduğunu da qəbul edə bilərsiniz.
Şəkil 5: Ayrılmış şokolad batonları
Şəkil 6: Dəlikli bir şokolad batonu
Şəkil 7: Dəlikli bir şokolad batonunun başqa bir nümunəsi
Çıxış verilənləri
Hər bir dataset üçün qaydalara uyğun olaraq kəsildikdən sonra əldə edilən şokolad parçalarının sayını göstərən bir sətir çıxarın. Çıxışda başqa simvollar icazə verilmir.