Neftin Üzərdən Yığılması
Müəyyən bir "yaşıl" resurs şirkətinə görə, yeni gəlirli bir neft toplama sənayesi yaranıb. Meksika Körfəzində üzən böyük xam neft ləkələri var ki, təşəbbüskar neft baronları tərəfindən toplanmağı gözləyir. Belə bir neft baronunun suyun səthindəki nefti toplamaq üçün xüsusi bir təyyarəsi var. Lakin, hər bir toplama 10m x 20m ölçüsündə bir düzbucaqlı əhatə edir (ya şərq/qərb, ya da şimal/cənub istiqamətində). Həmçinin, düzbucaqlının tamamilə neftlə örtülməsi tələb olunur, əks halda məhsul saf okean suyu ilə çirklənir və beləliklə gəlirsiz olur! Neft ləkəsinin xəritəsi verildikdə, neft baronu çıxarıla biləcək maksimum toplama sayını hesablamağınızı istəyir. Xəritə hər bir hüceyrənin 10m kvadrat suyu təmsil etdiyi N×N ölçülü bir şəbəkədir və hər bir hüceyrə ya neftlə örtülmüş, ya da saf su ilə işarələnmişdir.
Giriş verilənləri
Giriş bir tam ədəd K (1 ≤ K ≤ 100) ilə başlayır ki, bu da halların sayını göstərir. Hər bir hal bir tam ədəd N (1 ≤ N ≤ 600) ilə başlayır ki, bu da kvadrat şəbəkənin ölçüsünü göstərir. Növbəti N sətirin hər biri şəbəkədəki bir sıra hüceyrələri təmsil edən N simvoldan ibarətdir. '#' simvolu neftli hüceyrəni, '.' simvolu isə saf su hüceyrəsini təmsil edir.
Çıxış verilənləri
Hər bir hal üçün dəqiq olaraq belə formatlanmış bir sətir istehsal edilməlidir: "Hal X: M" burada X hal nömrəsidir (başlayaraq 1-dən) və M çıxarıla biləcək maksimum neft toplama sayıdır.