Soru 5 - Febehrance

İnsanlığın yavaş yavaş fizik gücüne dayalı aktivitelerden uzaklaşıp zekaya dayalı aktivitelere yoğunlaşmasını dikkate alan Uluslararası Olimpiyat Komitesi uzun tartışmalar sonucunda İngiltere‟de yapılacak 2012 Yaz Olimpiyatları için olimpiyatlara kas gücünden çok zekaya yönelik yeni bir oyun eklemeye karar verir. Yeni oyun için bir çok uzmandan öneri gelir. Çeşitli aşamalardan sonra komite oy birliği ile Prof. Dr. Gülşah Kandemir‟in önerisi olan “Febehrance” isimli oyunu olimpiyat takvimine eklemeye karar verir.

Febehrance Oyununun Kuralları

• Bu oyun her takımın sırayla sahada kendi çözümlerini sergilediği bir oyundur. Yani sahada aynı anda sadece bir takım bulunur.
• Oyun satrançta olduğu gibi küçük karelere bölünmüş bir alanda oynanır. Oyun alanı dikdörtgen şeklindedir.
• Her takım 9 oyuncudan oluşur.
• Her müsabakanın başında takımlara oyun sahasında oyuncularını yerleştirecekleri bir başlangıç dizilimi verilir ve bu başlangıç diziliminin nasıl olacağı oyunun başında hakem tarafından açıklanır. Dolayısıyla her müsabakada takımların başlangıç pozisyonları değişebilir.
• Oyunun amacı takım oyuncularının, başlangıç pozisyonlarından, kurallara uygun hamleler yaparak gene hakem tarafından oyunun başında açıklanan bitiş pozisyonlarına en az hamle yaparak ulaşmasıdır.
• Takımlar ne kadar az hamle yaparsa o kadar çok puan toplar.
• Sahada çözümü gösteren oyuncular sadece piyon vazifesi görürler. Çözümü hakemlere göstermekten başka bir vasıfları yoktur.
• Çözümün herhangi bir adımında herhangi bir takım oyuncusu hamle yapabilir. Diğer bir deyişle hangi oyuncun hareket edebileceği konusunda bir kısıtlama yoktur.

Kurallara Uygun Hamleler

Bu oyunda 2 çeşit hamle yapabilirsiniz. Takım oyuncularından biri ya komşu karelerden birine geçebilir ya da komşu karelerde bir arkadaşı varsa onun üstünden atlayarak bir öteki kareye geçebilir. Ayrıca şunu belirtmekte fayda var ki bir kez arkadaşının üzerinden zıplamaya başlayan oyuncu eğer komşu karesinde başka bir arkadaşı varsa onun da üzerinden atlayarak bir öteki kareye geçebilir. Ta ki komşu karesinde üzerinden atlayacak başka bir arkadaşı olmayan bir kareye gelene kadar. Bu belirtilenlerin hepsi bir hamle olarak sayılır. Yani takım oyuncularının birbirlerine yardımcı olabilecek pozisyonlarda durması takımın yapması gereken hamle sayısını azaltabilir.

Üstün zekaları ile dünyaya nam salmış fakat düşünsel eylemlere harcadıkları vakit nedeniyle antrenmanlara pek vakit ayıramamış ve bu yüzden de daha çok kas gücüne dayanan oyunları içeren olimpiyat oyunlarında bugüne kadar pek başarılı olamamış Eyitrük Cumhuriyeti için bu oyun altın madalya kazanabilmek adına harika bir şans olmuştur. Yeni bir oyun eklendiğini öğrenen Eyitrük Cumhuriyet‟i başbakanı Ahmet Kürşat Elden sağ kolu Eray Molla‟ya hemen bir emir verir: “Bize en iyi antrenörü bul!” Eray Bey biraz araştırdıktan sonra takımın başına, çeşitli çözülemeyecek derecede zor problemlerin çözümlerini optimize ederek dünyaya ün salmış Prof. Dr. Yıldız Ebru Çetin‟i getirmeye karar verir. Sizin göreviniz Dr. Çetin‟e takımımızın altın madalya kazanabilmesi için kullanması gereken taktikleri üretecek bir program hazırlamak.

Varsayımlar

• Oyun alanı yatayda N, dikeyde M kareden oluşmaktadır. (8 ≤ N, M ≤ 15).
• Bir oyuncu komşu karedeki takım arkadaşının üzerinden atladıktan sonra, bir başkasının üzerinden atlayarak hamlesine devam edebilir. Bu şekilde üzerinden atlanabilinecek oyuncu sayısında bir kısıt yoktur. Bu işlemin tamamı tek bir hamle kabul edilir.
• Hamle yapılacak kare boş olmalıdır. Dolayısıyla bir karede en fazla bir oyuncu bulunabilir.
• Yapılacak hamleler dikey ya da yatay olmalıdır. Çapraz hamle yasaktır.
• Oyuncular oyun sahası dışına çıkamazlar.
• Başlangıçta her zaman sahada 9 tane oyuncu vardır.
• Bir oyuncu oyuna bitiş noktasında başlayamaz.
• Bir oyuncunun herhangi bir bitiş noktasına gelmesi yeterlidir. Oyuncu ve bitiş noktalarının veriliş sırası önemsizdir.
• Her karenin her bir kenarı bir pozitif tamsayı ile numaralandırılmıştır. Buna göre en güneydeki ve en batıdaki kenarların numaralandırılması 1'den başlamaktadır. Eğer batı- doğu eksenindeki kenar numaralarına "x", güney-kuzey eksenindeki kenar numaralarına "y" denirse: 1 ≤ x ≤ N, 1 ≤ y ≤ M 'dir.
• Her bir kare "x y" şeklinde ifade edilmektedir.
• Programınız girdileri "febehrance.gir" isimli dosyadan okuyup, çıktıları "febehrance.cik" isimli dosyaya yazmalıdır.

Girdi (febehrance.gir)

Girdi dosyasının ilk satırında N ve M tamsayıları sırası ile verilecektir. Bundan sonraki 9 satırda oyuncuların başlangıç pozisyonları (kareleri) “x y” şeklinde verilecektir. Son 9 satırda da bitiş pozisyonları (kareleri) “x y” şeklinde verilecektir.

Çıktı (febehrance.cik)

Çıktı dosyasının ilk satırında toplam hamle sayısı verilmelidir. Bunu takip eden satırlarda ise her bir hamle bir satır olmak üzere hamleleriniz doğru bir formatta yer almalıdır.

Hamle Formatı:

• Her bir satır hamle yapacak oyuncunuzun bulunduğu karenin koordinatı ile başlar.
• Eğer oyuncunuz boş olan komşu bir kareye hamle yapıyorsa bu hamle gittiği yönün baş harfi ile belirtilir. Kuzey için "K", Güney için "G", Doğu için "D" ve Batı için "B".
• Eğer oyuncunuz bir arkadaşının üzerinden atlıyorsa bu hamle, gittiği yönün baş harfinin 2 kere bitişik yazılması ile belirtilir. Kuzey için "KK", Güney için "GG", Doğu için "DD" ve Batı için "BB".
• Eğer oyuncu bir hamlede birden fazla arkadaşının üzerinden atlıyorsa bunların arasına boşluk bırakılarak gösterilir. Örneğin; önce kuzeydeki sonra batıdaki sonra tekrar kuzeydeki bir arkadaşının üzerinden atlayarak hamle tamamlanacaksa bu: "KK BB KK" şeklinde belirtilir.

Yapabileceğiniz ve yapamayacağınız hamlelerin örnekleri

Örnek