Antenanın yerləşdirilməsi

Qlobal aeronaviqasiya elmi-tədqiqat mərkəzinə İsveçdə beşinci nəsil mobil telefon şəbəkələrinin qurulması tapşırığı verilib. Onların bu işi almasının əsas səbəbi yeni, çox səs-küyə bənzər antenanın kəşfidir. Bu antena 4DAir adlanır və dörd növdə təqdim olunur. Hər bir növ yalnız Yer kürəsinin qarşılıqlı elektromaqnit sahəsi səbəbindən (bir qədər əyilmiş) enlik və uzunluq şəbəkəsi ilə birləşdirilmiş istiqamətdə siqnalları ötürə və qəbul edə bilir. Bu dörd növ müvafiq olaraq şimal, qərb, cənub və şərq istiqamətlərində işləyən antenalara uyğundur. Aşağıda maraqlı yerlərin on iki kiçik halqa ilə təsvir edildiyi və onları əhatə edən ellipslər şəklində təsvir edilmiş doqquz 4DAir antenasının bir nümunə şəkli verilmişdir.

Aydındır ki, mümkün qədər az antenadan istifadə etmək arzuolunandır, lakin yenə də hər bir maraqlı obyekt üçün əhatə təmin edilməlidir. Tapşırığı aşağıdakı kimi modelləşdirək: qoy A - İsveçin səthini təsvir edən düzbucaqlı matrisa olsun, burada nöqtə ya ən azı bir antena ilə əhatə olunmalı olan maraq nöqtəsi, ya da boş yer olur. Antenalar A matrisasının istənilən yerində yerləşdirilə bilər. Antena r satırında və c sütununda yerləşdirildikdə, bu nöqtə əhatə olunmuş hesab edilir, lakin həmçinin antenanın yerləşdirilmə növündən asılı olaraq qonşu nöqtələrdən biri (c + 1, r), (c, r + 1), (c - 1, r) və ya (c, r - 1) əhatə olunur. A matrisasındakı bütün maraq nöqtələrini əhatə etmək üçün lazım olan ən az antena sayı nə qədərdir?

Giriş məlumatları

Birinci sətir ssenarilərin sayı n-i ehtiva edir. Hər bir ssenari iki natural ədəd h və w (1 < h < 40, 0 < w < 10) ehtiva edən sətirlə başlayır. Sonra h sətirdən ibarət olan A matrisi verilir, hər biri [*, o] dəstindən w simvolu ehtiva edir. * simvolu maraq simvolunu, o simvolu isə açıq məkanı təmsil edir.

Çıxış məlumatları

Hər bir ssenari üçün ayrıca sətirdə ssenari matrisasındakı bütün * elementlərini əhatə etmək üçün lazım olan minimal antena sayını çıxarın.