إريك يطفئ الضوء
Problem
يعمل إريك كحارس أمن في الجامعة ، لذلك بعد يوم من العمل يتجول في المبنى ويطفئ الأنوار ليلاً.
يتكون المبنى من عدد طوابق وسلالمين على اليسار واليمين. توجد غرف م في كل طابق بمحاذاة الممر الذي يربط السلمين الأيمن والأيسر. بمعنى آخر ، يمكن تمثيل المبنى كمستطيل به عدد n من الصفوف و m & thinsp؛ + & thinsp؛ 2 ، حيث يكون العمود الأول والأخير & nbsp؛ & mdash؛ السلالم ، وأعمدة م في الوسط و [مدش] ؛ غرف.
يقف إريك الآن في الطابق الأول على الدرج الأيسر. إنه يريد إطفاء الأنوار في كل مكان ، بينما لا يريد الصعود إلى الأرض أعلاه قبل إطفاء جميع الأضواء الموجودة على الأرضية الحالية. بالطبع ، يجب أن يكون إريك في الغرفة لإطفاء الأنوار. يقضي إريك دقيقة واحدة في صعود الدرج في طابق واحد أو الذهاب إلى الغرفة / الدرج المجاور من الغرفة المجاورة أو الدرج الموجود في نفس الطابق. إطفاء الأنوار في الغرفة التي يتواجد فيها إريك لا يأخذ وقته. & nbsp؛
ساعد إريك في العثور على الحد الأدنى من الوقت لإطفاء جميع الأضواء في المبنى.
لاحظ أن إريك ليس مضطرًا للعودة إلى موقعه الأصلي ، كما أنه غير مطالب بزيارة الغرف التي أضاءت فيها الأضواء بالفعل.
الإدخال:
يحتوي السطر الأول على عددين صحيحين n و m (1 & thinsp؛ & le؛ & thinsp؛ n & thinsp؛ & le؛ & thinsp؛ 15، 1 & thinsp؛ & le؛ & thinsp؛ m & thinsp؛ & le؛ & thinsp؛ 100) & mdash؛ عدد الطوابق وعدد الغرف في كل طابق على التوالي.
تحتوي الأسطر n التالية على وصف للمبنى. يحتوي كل سطر على سلسلة من الأصفار والآحاد بطول m & thinsp ؛ + & thinsp ؛ 2 تصف طابقًا واحدًا (الدرج الأيسر ، ثم m الغرف ، ثم السلم الأيمن) ، حيث يعني 0 أن الأضواء مطفأة و 1 تعني أن الأضواء مضاءة. يتم ترتيب الطوابق من الأعلى إلى الأسفل ، على وجه الخصوص ، يصف السطر الأخير الطابق الأول.
الحرفان الأول والأخير من كل سطر يصفان الدرج ، لذلك هما دائمًا 0.
الإخراج:
طباعة رقم واحد و [مدش] ؛ أقل وقت ممكن لإطفاء جميع الأضواء.
أمثلة:
نبسب ؛
<الجسم>
| إدخال |
الإخراج |
2 2
0010
0100 |
5 |
3 4
001000
000010
000010 |
12 |
التفسيرات:
في المثال الأول ، سيذهب إريك أولاً إلى الغرفة & nbsp؛ 1 & nbsp؛ في الطابق الأول ، ثم & nbsp؛ & mdash؛ إلى الغرفة & nbsp؛ 2 & nbsp؛ في الطابق الثاني باستخدام أي سلم.
في المثال الثاني ، سيذهب أولاً إلى الغرفة الرابعة في الطابق الأول ، ويصعد طابقًا واحدًا على الدرج الأيمن ، ويدخل الغرفة الرابعة في الطابق الثاني ، ثم يصعد الدرج الأيمن مرة أخرى ، ثم ينتقل إلى الطابق الثاني غرفة في الطابق الأخير.