Fırlanma Oyunu
Taxtanın hündürlüyü iki və eni W olan bir lövhəniz var. Lövhə 1×1 ölçülü hüceyrələrə bölünmüşdür. Lövhənin hər bir sıra yuxarıdan aşağıya doğru 1 və 2 ilə, hər bir sütun isə soldan sağa doğru 1 -dən W-ə qədər nömrələnmişdir. i-ci sırada və j-ci sütunda olan bir hüceyrəni (i, j) ilə göstəririk. Əvvəlcə, bəzi damalar lövhənin bəzi hüceyrələrinə yerləşdirilib. Burada hər bir damanın eyni göründüyünü qəbul edirik. Beləliklə, hər bir damanı fərqləndirmirik. Lövhədə aşağıdakı əməliyyatları yerinə yetirməyə icazə verilir:
Kvadrat fırlatma: Lövhədə 2×2 ölçülü bir kvadrat seçin. Sonra 2×2 kvadrat içindəki damaları elə hərəkət etdirin ki, damalar kvadrat içindəki mövqelərini 90 dərəcə saat əqrəbi istiqamətində və ya əks istiqamətdə fırlatsınlar.
Üçbucaq fırlatma: Lövhədə üçbucaq əmələ gətirən hüceyrələr dəstini seçin. Burada, bir hüceyrə dəstini üçbucaq adlandırırıq, əgər bu dəst 2×2 kvadratından dəqiq bir hüceyrə çıxarılaraq əmələ gəlirsə. Kvadrat fırlatma ilə oxşar şəkildə, seçilmiş üçbucaq içindəki damaları saat əqrəbi istiqamətində və ya əks istiqamətdə fırladın.
Bu problemin məqsədi, damaların düzülüşünü fırlatma əməliyyatları ardıcıllığı ilə istənilən düzülüşə çevirməkdir. Başlanğıc düzülüş və hədəf düzülüş haqqında məlumatlar giriş olaraq verilir. İstənilən düzülüş üçün hər bir hüceyrə (i, j) üçün aşağıdakılardan biri göstərilir: i. hüceyrə (i, j) dama içərməlidir, ii. hüceyrə (i, j) dama içərməməlidir, və ya iii. hüceyrə (i, j) üçün heç bir məhdudiyyət yoxdur. Düzülüşün məhdudiyyətləri təmin etməsi üçün damaları hərəkət etdirmək üçün tələb olunan minimum əməliyyat sayını hesablayın və onu çıxış edin.
Giriş verilənləri
Giriş aşağıdakı kimi formatlanmışdır.
W
s_11s_11…s_1W
s_21s_21…s_2W
t_11t_11…t_1W
t_21t_21…t_2W
Girişin ilk sətri lövhənin eni olan W (2 ≤ W ≤ 2000) tam ədədini ehtiva edir. Sonrakı iki sətir başlanğıc düzülüş haqqında məlumatları ehtiva edir. Əgər başlanğıc düzülüşdə bir hüceyrə (i, j) dama ehtiva edirsə, s_ij o-dur. Əks halda, s_ij .-dır. Sonra boş bir sətir gəlir. Sonrakı iki sətir istənilən düzülüş haqqında məlumatları ehtiva edir. Eyni şəkildə, əgər son olaraq bir hüceyrə (i, j) dama ehtiva etməlidirsə, t_ij o-dur. Əgər son olaraq bir hüceyrə (i, j) dama ehtiva etməməlidirsə, t_ij .-dır. Əgər bir hüceyrə (i, j) üçün heç bir şərt yoxdursa, t_ij *-dır. Həmişə bir həllin mövcud olduğunu qəbul edə bilərsiniz.
Çıxış verilənləri
Bir sətirdə tələb olunan minimum əməliyyat sayını çıxış edin.