Problem
Eric travaille comme agent de sécurité à l'université, donc après une journée de travail, il se promène dans le bâtiment et éteint les lumières la nuit.
Le bâtiment a n étages et deux escaliers à gauche et à droite. Il y a m chambres à chaque étage le long du couloir qui relie les escaliers gauche et droit. En d'autres termes, le bâtiment peut être représenté sous la forme d'un rectangle à n lignes et m&minsp;+&minsp;2 colonnes, où la première et la dernière colonne — escaliers, et m colonnes au milieu — chambres.
Eric se tient maintenant au premier étage sur l'escalier de gauche. Il veut éteindre les lumières partout, alors qu'il ne veut pas monter à l'étage supérieur avant d'avoir éteint toutes les lumières de l'étage actuel. Évidemment, Eric doit être dans la pièce pour éteindre les lumières. Eric passe une minute à monter les escaliers d'un étage ou à se rendre dans la pièce / les escaliers d'à côté depuis la pièce voisine ou les escaliers du même étage. Éteindre les lumières dans la pièce où se trouve Eric ne prend pas son temps.
Aidez Eric à trouver le temps minimum pour éteindre toutes les lumières du bâtiment.
Notez qu'Eric n'a pas à retourner à son poste d'origine, et aussi qu'il n'est pas obligé de visiter des pièces où les lumières sont déjà éteintes.
Saisie :
La première ligne contient deux entiers n et m (1 ≤ n ≤ 15, 1 ≤ m ≤ 100) — le nombre d'étages et le nombre de pièces à chaque étage, respectivement.
Les n lignes suivantes contiennent une description du bâtiment. Chaque ligne contient une chaîne de zéros et de uns de longueur m+&minsp;2 décrivant un étage (escalier de gauche, puis m pièces, puis escalier de droite), où 0 signifie que les lumières sont éteintes et 1 signifie que les lumières sont allumées. Les étages sont donnés dans l'ordre de haut en bas, en particulier, la dernière ligne décrit le premier étage.
Les premier et dernier caractères de chaque ligne décrivent les escaliers, ils sont donc toujours 0.
Sortie :
Imprimer un numéro — le temps minimum possible nécessaire pour éteindre toutes les lumières.
Exemples :
| Entrée |
Sortie |
2 2
0010
0100 |
5 |
3 4
001000
000010
000010 |
12 |
Explications :
Dans le premier exemple, Eric ira d'abord dans la chambre 1 au premier étage, puis — à la chambre 2 au deuxième étage en utilisant n'importe quelle échelle.
Dans le deuxième exemple, il ira d'abord dans la quatrième pièce du premier étage, montera d'un étage par l'escalier de droite, entrera dans la quatrième pièce du deuxième étage, remontera à nouveau l'escalier de droite, passera au deuxième chambre au dernier étage.