Domino döşəməsi#7318
Bu tapşırıqda sizdən domino daşları ilə örtülmüş bir düzbucaqlı örtüyü digərinə çevirmək tələb olunur, bunu domino daşlarını dövrlər üzrə hərəkət etdirərək etməlisiniz.
Gəlin h × w ölçülü düzbucaqlı şəbəkəni nəzərdən keçirək. Domino daşı (və ya sadəcə domino) bir-birinə bitişik olan hər hansı iki şəbəkə hüceyrəsinə yerləşdirilə bilən düzbucaqlı blokdur. Şəbəkənin örtülməsi, şəbəkənin hər bir hüceyrəsinin dəqiq bir domino ilə örtüldüyü bir domino dəstidir. Qeyd edək ki, domino daşları şəbəkənin sərhədini keçə bilməz.
Sizə şəbəkənin iki örtülməsi verilir: başlanğıc və son. Sizin vəzifəniz başlanğıc örtülməni son örtülməyə çevirməkdir. Bunu etmək üçün gedişlər edə bilərsiniz. Bir gediş domino dövrünü seçmək və bu dövr üzrə hərəkət etməkdən ibarətdir (rəsmi tərif aşağıda verilmişdir). Hər gedişin dəyəri müvafiq domino dövründəki hüceyrələrin sayına bərabərdir. Ümumi çevrilmə dəyəri etdiyiniz bütün gedişlərin xərclərinin cəmidir. Təbii ki, ümumi dəyər mümkün olan ən az olmalıdır.
İndi detallara keçək.
Verilmiş örtülmədə müsbət uzunluqlu n domino dövrünü təyin edək. Gəlin 2n müxtəlif hüceyrədən ibarət dövri ardıcıllığı nəzərdən keçirək ki, ardıcıllıqda ardıcıl olan hər iki hüceyrə bir-birinə bitişikdir. "Dövri" o deməkdir ki, ardıcıllığın ilk və son hüceyrəsi qonşu sayılır. Belə ardıcıllıqda 2n cüt ardıcıl hüceyrə var. n cüt hüceyrəni n kəsişməyən domino daşları ilə örtək və domino dövrü əldə edək.
Domino daşlarının dövr üzrə hərəkəti örtülməni dəyişir. Əvvəlcə dövrə aid olan bütün 2n hüceyrəni örtən n domino daşları çıxarılır. Sonra n yeni kəsişməyən domino daşları əlavə edilir ki, n digər ardıcıl hüceyrə cütlərini örtsün. Nəticədə əldə edilən domino dəsti də örtülmədir. Xatırladaq ki, belə bir gedişin dəyəri 2n-ə bərabərdir.
Birinci sətir h və w (1 ≤ h, w ≤ 100) tam ədədlərini ehtiva edir: düzbucaqlı şəbəkənin hündürlüyü və eni.
Növbəti h sətirin hər biri w simvol ehtiva edir və başlanğıc örtülməni təsvir edir. Hər bir simvol aşağıdakılardan biridir:
“l” simvolu domino daşının sol hissəsini göstərir,
“r” simvolu domino daşının sağ hissəsini göstərir,
“u” simvolu domino daşının üst hissəsini göstərir,
“d” simvolu domino daşının alt hissəsini göstərir.
Növbəti sətir w tire (“-”) işarəsi ehtiva edir.
Növbəti h sətirin hər biri w simvol ehtiva edir və son örtülməni eyni formatda təsvir edir.
Giriş məlumatlarının düzgün olduğu təmin edilir:
h və w elə seçilmişdir ki, h× w şəbəkəsinin örtülməsi mümkündür
hər bir örtülmədə hər bir simvolun tələb olunan istiqamətdə uyğun qonşusu var
Birinci sətirdə iki ədəd yazın: m - gedişlərin sayı və p - çevrilmələrin ümumi dəyəri. p dəyəri minimal olmalıdır, m gedişlərin sayı isə istənilən ola bilər.
Növbəti m sətir hər bir gedişi təsvir etməlidir, hər biri bir sətirdə. k hüceyrədən ibarət domino dövrü üzrə gediş k r_1 c_1 r_2 c_2 ... r_k c_k şəklində yazılmalıdır. Burada r_i və c_i dövrün i-ci hüceyrəsinin koordinatlarıdır. Sətirdəki ədədlər bir və ya bir neçə boşluqla ayrılmalıdır. Dövr istənilən nöqtədən başlana və istənilən istiqamətdə keçilə bilər.
Nümunə 1
Birinci nümunədə ən kiçik ümumi dəyər 10-a bərabərdir. Bunu bir gedişlə əldə etmək olar ki, bu da şəbəkənin 10 sərhəd hüceyrəsini dövri qaydada əhatə edir. Hüceyrələri (1, 1) və (1, 2), (1, 3) və (1, 4), (2, 4) və (3, 4), (3, 3) və (3, 2), (3, 1) və (2, 1) örtən beş domino daşı çıxarılır. Sonra hüceyrələri (1, 2) və (1, 3), (1, 4) və (2, 4), (3, 4) və (3, 3), (3, 2) və (3, 1), (2, 1) və (1, 1) örtən yeni domino daşları əlavə edilir.
Həll solda şəkildə göstərilmişdir. Qeyd edək ki, son örtülməyə çatmaq üçün başqa yollar da var. Sağda optimal olmayan həll göstərilmişdir.
İkinci nümunədə ən kiçik ümumi dəyər 12-yə bərabərdir. Bunu hər biri dörd hüceyrədən ibarət olan üç kiçik dövr üzrə domino daşlarını hərəkət etdirərək əldə etmək olar. Həll aşağıda göstərilmişdir.
