问题 G: 看门人
题目描述
建筑由n层楼组成，左右两侧有楼梯。每层楼有m个房间在同一条线上，走廊连接左右楼梯，通过所有的房间。换句话说，该建筑可以表示为一个有n行和m+2列的矩形，其中第一列和最后一列表示楼梯，中间的m列表示房间。
Sagheer站在一楼左边的楼梯上。他想把所有的灯都关掉，这样他就不会上楼，直到他站的那层楼所有的灯都关掉。当然，Sagheer必须去一个房间把灯关掉。Sagheer使用楼梯到达下一层或从当前房间/楼梯移动到同一层的相邻房间/楼梯需要1分钟。在他所站的房间里，他很快就把灯关掉了。帮助Sagheer找到关掉所有灯的最短总时间。
请注意，Sagheer不必回到他的起始位置，他也不必去已经关灯的房间。
输入格式
第一行包含两个整数n和m（1≤n≤15和1≤m≤100) − 楼层数和每个楼层中的房间数。
接下来的n行包含建筑描述。每一行包含一个长度为m+2的二进制字符串，表示一个楼层（左楼梯，然后是m个房间，然后是右楼梯），其中0表示灯关闭，1表示灯打开。楼层从上到下列出，因此最后一行表示底层。
每个字符串的第一个和最后一个字符分别表示左楼梯和右楼梯，因此它们始终为0。
输出格式
打印单个整数− 关闭所有灯所需的最小总时间。
Examples
2 2 0010 0100
5
3 4 001000 000010 000010
12
4 3 01110 01110 01110 01110
18
在第一个例子中，Sagheer会去一楼的1号房间，然后他会使用左右楼梯去二楼的2号房间。 在第二个例子中，他会去一楼的第四个房间，走右边的楼梯，然后去二楼的第四个房间，再走右边的楼梯，然后去最后一层的第二个房间。 在第三个例子中，他将在每层左右楼梯之间交替穿过整个走廊
输入样例 复制
2 2
0010
0100输出样例 复制
5数据范围与提示
在第一个例子中，Sagheer会去一楼的1号房间，然后他会使用左右楼梯去二楼的2号房间。
在第二个例子中，他会去一楼的第四个房间，走右边的楼梯，然后去二楼的第四个房间，再走右边的楼梯，然后去最后一层的第二个房间。
在第三个例子中，他将在每层左右楼梯之间交替穿过整个走廊
