Soru 3 - Hırsız Hapsetme

Ödüllü Yüksek Mimar Yasemin Gökkaya yeni tasarladığı evin en son teknolojiyle donanmasını istemiştir. Ev o kadar donanımlıdır ki; ev boş iken hırsız girdiğinde, hırsızı içeride hapsedip polise haber vermektedir. Bu hırsız hapsetme mekanizması şöyle çalışmaktadır. Hırsız evin herhangi bir noktasındayken algılandığında alarm çalışmaktadır. Alarm çalışınca hırsız doğal olarak kendisine en yakın olan çıkış noktasına (örn. kapı veya pencere) yönelecektir. Hırsız tam bu çıkış noktasına geldiğinde, çıkış noktası metal bir kapak ile anında kapanacaktır. Bu anda hırsız doğal olarak bulunduğu noktaya en yakın, kapanmamış olan diğer bir çıkış noktasına yönelecektir. Buraya ulaştığında yine aynı şekilde metal kapak anında kapanacaktır. Hırsızı oyalamak için kullanılan bu sistem, hırsız bütün çıkışları deneyip son çıkış noktasına geldiğinde orayı da kapatarak hırsızı hapsedecektir. Sizden istenilen verilen bir duruma göre hırsızın ziyaret edeceği çıkış noktalarını sırası ile bulmaktır. Böylece programınız evin merkezi sistemine yüklenecek ve hırsız oyalanırken polisin gelmesi için zaman kazanılabilecektir.

Varsayımlar

• Ev iki boyutlu bir düzlem şeklindedir ve birim karelerden oluşmaktadır. Evin eni M, boyu N’dir. (2 < N, M ≤ 1000)
• Evdeki bazı kareler kapalı (duvarlar, eşyalar vb.), bazıları da açıktır (hırsızın hareket edebileceği alanlar).
• Dikdörtgen olan evin çevresi duvarlarla kaplıdır. Çıkış noktaları ise bu duvarlar üzerindeki tek karelik açıklıklardır. İki çıkış noktası komşu olamaz.
• Çıkış noktalarının sayısı K’dır (1 ≤ K ≤ 30).
• Hırsız herhangi bir anda bulunduğu noktadan; yukarı, aşağı, sağ ve sol olmak üzere komşu olan 4 kareden birine hareket edebilir.
• Hırsız yeni bir çıkış noktasına yönelmeye karar verirken, herhangi iki çıkış noktasının kendisine en yakın ve eşit uzaklıkta olacağı girdiler denenmeyecektir.
• Programınız girdiyi hapset.gir dosyasından okumalı, çıktıyı hapset.cik dosyasına aynen aşağıda belirtildiği gibi yazmalıdır.

Girdi (hapset.gir)

• Girdi dosyası hapset.gir’in ilk satırında evin boyutlarını gösteren sırasıyla N (satır sayısı) ve M (sütun sayısı) tamsayıları bulunacaktır.
• İkinci satırda hırsızın bulunduğu karenin sırasıyla satır ve sütun numaraları verilecektir. Sol üst köşe 0 0, sağ alt köşe N-1 M-1 şeklinde ifade edilmektedir.
• Takip eden N satırın her birinde M adet sayı (karenin bilgisi) aralarında birer boşlukla verilecektir. Her kare için 1 kapalı, 0 açık (hırsızın hareket edebileceği alanlar) anlamına gelmektedir.

Çıktı (hapset.cik)

• Programınız hapset.cik dosyasının ilk satırına çıkış noktası sayısını belirten bir adet tamsayı K yazacaktır.
• Takip eden K satırın her birine; sırası ile hırsızın ziyaret edeceği çıkış noktalarının sırası ile satır ve sütun numaraları aralarında birer boşluk bulunacak şekilde yazılacaktır. Sol üst köşe 0 0, sağ alt köşe N-1 M-1 şeklinde ifade edilmektedir.

Örnek