Plitələrin Oyunu#6601
Plitələr Oyunu, kvadrat hüceyrələrdən ibarət R sətir və C sütun şəklində düzbucaqlı lövhə üzərində iki oyunçu üçün oynanan bir oyundur. Oyunun əvvəlində bəzi plitələr qara rəngə boyana bilər, qalanları isə ağ qalır. Sonra, Oyunçu 1 və Oyunçu 2 növbə ilə hərəkət edir və etibarlı hərəkət edə bilməyən ilk oyunçu oyunu uduzur. Oyunun ilk hərəkəti Oyunçu 1 tərəfindən edilir və ağ plitə seçərək üzərinə 1 rəqəmi yazmaqdan ibarətdir. Bundan sonra, hər növbəti i hərəkəti, i-1 nömrəli plitəyə üfüqi və ya şaquli (amma diaqonal deyil) bitişik olan istifadə olunmamış ağ plitəyə i rəqəmini yazmaqdan ibarətdir. Qeyd edək ki, Oyunçu 1 həmişə tək rəqəmləri, Oyunçu 2 isə həmişə cüt rəqəmləri yazır.
Aşağıdakı şəkil, oyun zamanı R = 3 və C = 4 olan lövhənin mümkün konfiqurasiyalarının üç nümunəsini göstərir. Solda başlanğıc konfiqurasiyanı göstərir. Ortada, boz rəngdə olan hüceyrələr Oyunçu 2 üçün mümkün hərəkətləri işarələyir. Sağda isə, uyğun hərəkəti seçən Oyunçu 2 tərəfindən oyunun qazanıldığı konfiqurasiyanı göstərir.
Sizin vəzifəniz, lövhənin başlanğıc konfiqurasiyası verildikdə, hər iki oyunçu optimal oynayarsa, hansı oyunçunun qazanacağını müəyyən edən bir proqram yazmaqdır.
Hər test halı bir neçə sətir istifadə edərək təsvir edilir. İlk sətir, lövhənin sətir və sütun sayını təmsil edən iki tam ədəd R və C ehtiva edir (1 ≤ R, C ≤ 50). Növbəti R sətirin i-ci sətiri, başlanğıc lövhənin i-ci sətirini təsvir edən C simvoldan ibarət B_i sətirini ehtiva edir. B_i-nin j-ci simvolu ya '.' (nöqtə) ya da böyük hərflə 'X' hərfidir, müvafiq olaraq i-ci sətir və j-ci sütundakı plitənin ağ və ya qara olduğunu göstərir. Hər test halında ən azı bir plitə ağdır.
Hər test halı üçün, hər iki oyunçu optimal oynayarsa, oyunu qazanacaq oyunçunun nömrəsini (1 və ya 2) təmsil edən bir tam ədəd ilə bir sətir çıxarın.
Nümunə 1