Döyüş gəmiləri

Yəqin ki, "Battleships" oyununun qələm və kağız versiyasını bilirsiniz, amma biz onu təsvir edərkən diqqətlə dinləyin: Hər bir tapmaca gizli yerləşdirilmiş 10 fərqli gəmidən ibarət olan 10-dan 10-a qədər kvadrat şəbəkədən ibarətdir. Bu gəmilərdən biri 4 kvadrat uzunluğundadır, ikisi 3 kvadrat uzunluğundadır, üçü 2 kvadrat uzunluğundadır və qalan dörd gəmi isə hər biri 1 kvadrat uzunluğundadır. İki gəmi bir-birinin üstündə ola bilməz və heç biri digərinə hətta diaqonal olaraq yaxın ola bilməz. Gəmilərin yerləşdirilməsi ilə bağlı yeganə ipucları şəbəkənin solunda və aşağısında verilmiş sıra və sütun cəmləridir. Hər bir sıra/sütun cəmi həmin sıra/sütunda gəmilər tərəfindən tutulan kvadratların sayını göstərir. Aşağıdakı şəkillər "Battleships" tapmacasının və onun həllinin nümunəsini göstərir.

Şəkil 1

"Battleships" tapmacası hazırlayarkən, verilmiş sıra və sütun cəmləri üçün unikal həllin olduğuna əmin olmalısınız. Bəzən yanlardakı cəmlər unikal həllin təmin edilməsi üçün kifayətdir (yuxarıdakı nümunə kimi), lakin bəzən bütün həlləri istisna etmək üçün şəbəkədə bir və ya daha çox kvadrat göstərməlisiniz (aşağıdakı nümunədə olduğu kimi).

Şəkil 2

Bu göstərilən kvadratlar yeddi növdən biri ola bilər: su, gəminin içi, üfüqi gəminin sol ucu, şaquli gəminin üst ucu, üfüqi gəminin sağ ucu, şaquli gəminin alt ucu və 1-kvadrat gəmi. Bunlar növbəti səhifənin yuxarısında göstərilmişdir. Hər kvadratın altındakı simvollar çıxışınız üçün istifadə olunacaq. Qeyd edək ki, son simvol böyük hərf 'O'dur, sıfır deyil; həmçinin 'X' böyük hərfdir, lakin 'w' və 'v' kiçik hərfdir.

Şəkil 3

Sizin vəzifəniz aşağıdakıdır: sıra və sütun cəmləri dəsti verildikdə, unikal həllin təmin edilməsi üçün lazım olan minimum göstərilən kvadratların sayını tapmalısınız. Əgər bu rəqəm 2-dən böyükdürsə, tapmacanı çox qeyri-müəyyən olaraq rədd etməlisiniz.

Əks halda, unikal həllin təmin edilməsi üçün istifadə edilə bilən "ən yaxşı" kvadrat(lar)ın yerini və istifadə ediləcək kvadrat növünü Şəkil 3-də göstərilən simvollarla birlikdə çıxış edin. Tək kvadrat halında, "ən yaxşı" kvadrat ən aşağı sıra nömrəsinə malik olan kvadratdır, hər hansı bərabərlikləri ən aşağı sütun nömrəsinə malik olanı seçərək pozun. Bundan sonra, istifadə ediləcək kvadrat növü arasında seçim varsa, leksikoqrafik olaraq birinci olanı istifadə edin, burada leksikoqrafik sıralama Şəkil 3-də göstərilmişdir, "su" leksikoqrafik olaraq birinci kvadrat növüdür, sonra "gəminin içi" və s. İki kvadrat halında, bütün birinci kvadratlar arasında ən yaxşı olan birinci kvadratı olan cütü çıxış edin, bərabərlikləri ən yaxşı ikinci kvadratı seçərək pozun. Bütün sıra və sütun nömrələri 1-dən başlayır.