Problem
Eric arbeitet als Wachmann an der Universität, so dass er nach Arbeitszeiten durch das Gebäude geht und das Licht für die Nacht ausschaltet.
Im N-Floor-Gebäude und zwei Treppen nach links und rechts. Jede Etage verfügt über m Zimmer entlang des Korridors, die die linke und rechte Treppe verbindet. Mit anderen Worten, das Gebäude kann als Rechteck von n Linien und m + 2 Säulen präsentiert werden, wo die erste und letzte Säulen sind Treppen und m Säulen in der Mitte sind Zimmer.
Eric steht im ersten Stock auf der linken Treppe. Er will die Lichter überall ausschalten, und er will nicht auf den Boden über den Lichtern auf dem aktuellen Stock hinaufgehen. Natürlich sollte Eric im Raum sein, um die Lichter auszuschalten. Eric verbringt eine Minute klettern die Treppe auf einer Etage oder bewegt sich zu einem nächsten Zimmer / zu einer Leiter aus dem nächsten Zimmer oder von der Treppe auf der gleichen Etage. Das Lichtausschalten im Raum, in dem Eric ist, nimmt seine Zeit nicht.
Hilf Eric, eine Mindestzeit zu finden, um das Licht im Gebäude abzuschalten.
Beachten Sie, dass Eric nicht zu seinem Ausgangspunkt zurückkehren sollte und dass er nicht verpflichtet ist, Räume zu besuchen, in denen die Lichter bereits abgeschaltet sind.
Eingabe:Die erste Zeile enthält zwei ganze Zahlen n und m (1 n ≤ 15, 1 ≤ 100) - die Anzahl der Stockwerke und die Anzahl der Räume auf jedem Stockwerk.
Die folgenden n Linien beschreiben das Gebäude. Jede Linie enthält eine Linie von Null und Länge m + 2 beschreiben eine Etage (links, dann m Zimmer, dann rechte Treppe), wobei 0 bedeutet, dass das Licht aus ist und 1 bedeutet, dass das Licht eingeschaltet ist. Diese sind von oben nach unten, insbesondere die letzte Zeile beschreibt den ersten Stock.
Die ersten und letzten Symbole jeder Linie beschreiben die Treppe, so dass sie immer gleich 0 sind.
Ausgangsdaten:Nehmen Sie eine Nummer aus, die minimal mögliche Zeit, um das Licht ausschalten.
Beispiele:| Eingangsdaten | Ausgangsdaten |
2
ANHANG
0100 | 5. |
Artikel 4
ANHANG
010
010 | 12 |
Beschreibung:Im ersten Beispiel wird Eric zunächst in den ersten Stock und dann in den zweiten Stock mit jedem Treppenhaus in den Raum 1 gehen.
Im zweiten Beispiel geht er in den vierten Raum im ersten Stock, geht ein Stock auf der rechten Treppe hinauf, geht in den vierten Raum im zweiten Stock, geht die rechte Treppe zurück, geht in den zweiten Raum im letzten Stock.