Problem
Eric üniversitede güvenlik görevlisi olarak çalışıyor, bu yüzden bir günlük işten sonra binanın içinde dolaşıyor ve geceleri ışıkları kapatıyor.
Bina n katlıdır ve sağda ve solda iki merdiven vardır. Sağ ve sol merdivenleri birbirine bağlayan koridor boyunca her katta m oda bulunmaktadır. Başka bir deyişle, bina n sıralı ve m + 2 sütunlu bir dikdörtgen olarak temsil edilebilir; burada ilk ve son sütun — merdivenler ve ortada m sütunlar — odalar.
Eric şimdi birinci katta sol merdivenlerde duruyor. Bulunduğu katın tüm ışıklarını kapatmadan bir üst kata çıkmak istemezken her yerin ışıklarını kapatmak ister. Tabii ki, Eric ışıkları kapatmak için odada olmalı. Eric bir dakikayı bir kat merdiven çıkarak veya bir sonraki odadan bir sonraki odaya/merdivenlere veya aynı kattaki merdivenlere çıkarak geçiriyor. Eric'in bulunduğu odadaki ışıkları söndürmesi zamanını almıyor.
Eric'in binadaki tüm ışıkları söndürmek için gereken minimum süreyi bulmasına yardım edin.
Eric'in orijinal konumuna geri dönmesi gerekmediğini ve ayrıca ışıkların zaten kapalı olduğu odaları ziyaret etmesi gerekmediğini unutmayın.
Giriş:
İlk satır iki tamsayı içerir n ve m (1 ≤ n ≤ 15, 1 ≤ m ≤ 100) — sırasıyla kat sayısı ve her kattaki oda sayısı.
Sonraki n satır, binanın bir tanımını içerir. Her satır, bir katı (sol merdiven, sonra m oda, sonra sağ merdiven) tanımlayan m + 2 uzunluğunda bir sıfır ve bir dizisi içerir; burada 0, ışıkların kapalı olduğu ve 1, ışıkların açık olduğu anlamına gelir. Katlar yukarıdan aşağıya doğru sıralanmıştır, özellikle son satır birinci katı anlatmaktadır.
Her satırın ilk ve son karakterleri merdivenleri tanımlar, dolayısıyla her zaman 0'dır.
Çıktı:
Bir sayı yazdır — tüm ışıkları kapatmak için gereken minimum süre.
Örnekler:
| Giriş |
Çıktı |
2 2
0010
0100 |
5 |
3 4
001000
000010
000010 |
12 |
Açıklamalar:
İlk örnekte, Eric önce birinci kattaki 1 odaya gidecek ve ardından — herhangi bir merdivenle ikinci kattaki 2. odaya çıkın.
İkinci örnekte, önce birinci kattaki dördüncü odaya gidecek, sağdaki merdivenlerden bir kat çıkacak, ikinci kattaki dördüncü odaya girecek, sağdaki merdivenlerden tekrar çıkacak, ikinciye gidecek. oda son kattadır.