Kapitan Q-nin Xəzinəsi
Sizdə məşhur quldur "Kapitan Q" tərəfindən çəkilmiş köhnə bir xəritə var. Bu xəritə adada basdırılmış bir çox xəzinə sandığının yerlərini göstərir.
Xəritə kvadrat bölmələrə bölünmüşdür və hər bölmədə ya bir rəqəm var, ya da yoxdur. Rəqəm, özünü və 8 qonşusunu əhatə edən 9 qonşu bölmədəki sandıqların sayını göstərir. Hər bölmədə ən çox bir sandıq olduğunu qəbul edə bilərsiniz.
Xəritəyə baxmayaraq, sandıqların basdırıldığı bölmələri müəyyən edə bilmirsiniz. Hətta adada basdırılmış sandıqların ümumi sayı da məlum deyil. Lakin, adada basdırılmış minimum sandıq sayını hesablamaq mümkündür. Bu problemdəki missiyanız, bunu hesablaya biləcək bir proqram yazmaqdır.
Giriş verilənləri
Giriş, məlumat dəstlərinin ardıcıllığıdır. Hər bir məlumat dəsti aşağıdakı kimi formatlanmışdır.
h w xəritə
Məlumat dəstinin ilk sətri iki müsbət tam ədəddən ibarətdir: h və w. h xəritənin hündürlüyü, w isə xəritənin enidir. 1 ≤ h ≤ 15 və 1 ≤ w ≤ 15 olduğunu qəbul edə bilərsiniz.
Növbəti h sətir xəritəni verir. Hər sətir w simvoldan ibarətdir və xəritənin üfüqi zolağına uyğun gəlir. Sətirdəki hər bir simvol bölmənin vəziyyətini aşağıdakı kimi göstərir.
'.': Bölmə adanın bir hissəsi deyil (su). Burada sandıq yoxdur.
'*': Bölmə adanın bir hissəsidir və 9 qonşusundakı sandıqların sayı məlum deyil.
'0'-'9': Bölmə adanın bir hissəsidir və rəqəm 9 qonşusundakı sandıqların sayını göstərir.
Xəritənin öz-özünə zidd olmadığını, yəni ən azı bir sandıq düzülüşünün olduğunu qəbul edə bilərsiniz. Həmçinin, rəqəmlərlə olan bölmələrin sayının ən azı bir və ən çox 15 olduğunu qəbul edə bilərsiniz.
İki sıfırdan ibarət bir sətir girişin sonunu göstərir.
Çıxış verilənləri
Hər bir məlumat dəsti üçün, minimum sandıq sayını ehtiva edən bir sətir çıxarın. Çıxışda başqa heç bir simvol olmamalıdır.