ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

4188: 看门人

内存限制：128 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：8 通过：5
提交提交记录统计Web Board

题目描述


有些人下班时把工作场所的灯开着，这是一种资源浪费。作为DHBW的校长，Sagheer等到所有的学生和教授都离开了教学楼，然后走过去把所有的灯都关了。

建筑由n层楼组成，左右两侧有楼梯。每层楼有m个房间在同一条线上，走廊连接左右楼梯，通过所有的房间。换句话说，该建筑可以表示为一个有n行和m+2列的矩形，其中第一列和最后一列表示楼梯，中间的m列表示房间。

Sagheer站在一楼左边的楼梯上。他想把所有的灯都关掉，这样他就不会上楼，直到他站的那层楼所有的灯都关掉。当然，Sagheer必须去一个房间把灯关掉。Sagheer使用楼梯到达下一层或从当前房间/楼梯移动到同一层的相邻房间/楼梯需要1分钟。在他所站的房间里，他很快就把灯关掉了。帮助Sagheer找到关掉所有灯的最短总时间。

请注意，Sagheer不必回到他的起始位置，他也不必去已经关灯的房间。

Some people leave the lights at their workplaces on when they leave that is a waste of resources. As a hausmeister of DHBW, Sagheer waits till all students and professors leave the university building, then goes and turns all the lights off.
The building consists of n floors with stairs at the left and the right sides. Each floor has m rooms on the same line with a corridor that connects the left and right stairs passing by all the rooms. In other words, the building can be represented as a rectangle with n rows and m+2 columns, where the first and the last columns represent the stairs, and the m columns in the middle represent rooms.
Sagheer is standing at the ground floor at the left stairs. He wants to turn all the lights off in such a way that he will not go upstairs until all lights in the floor he is standing at are off. Of course, Sagheer must visit a room to turn the light there off. It takes one minute for Sagheer to go to the next floor using stairs or to move from the current room/stairs to a neighboring room/stairs on the same floor. It takes no time for him to switch the light off in the room he is currently standing in. Help Sagheer find the minimum total time to turn off all the lights.
Note that Sagheer does not have to go back to his starting position, and he does not have to visit rooms where the light is already switched off.

Input
The first line contains two integers n and m (1≤n≤15 and 1≤m≤100) − the number of floors and the number of rooms in each floor, respectively.
The next n lines contains the building description. Each line contains a binary string of length m+2 representing a floor (the left stairs, then m rooms, then the right stairs) where 0 indicates that the light is off and 1 indicates that the light is on. The floors are listed from top to bottom, so that the last line represents the ground floor.
The first and last characters of each string represent the left and the right stairs, respectively, so they are always 0.
Output
Print a single integer − the minimum total time needed to turn off all the lights.
Examples
Input 
2 2
0010
0100
Output 
5
Input 
3 4
001000
000010
000010
Output 
12
Input 
4 3
01110
01110
01110
01110
Output 
18
Note
In the first example, Sagheer will go to room 1 in the ground floor, then he will go to room 2 in the second floor using the left or right stairs.
In the second example, he will go to the fourth room in the ground floor, use right stairs, go to the fourth room in the second floor, use right stairs again, then go to the second room in the last floor.
In the third example, he will walk through the whole corridor alternating between the left and right stairs at each floor.

输入格式

第一行包含两个整数n和m（1≤n≤15和1≤m≤100) − 楼层数和每个楼层中的房间数。

接下来的n行包含建筑描述。每一行包含一个长度为m+2的二进制字符串，表示一个楼层（左楼梯，然后是m个房间，然后是右楼梯），其中0表示灯关闭，1表示灯打开。楼层从上到下列出，因此最后一行表示底层。

每个字符串的第一个和最后一个字符分别表示左楼梯和右楼梯，因此它们始终为0。

输出格式

打印单个整数− 关闭所有灯所需的最小总时间。

Examples

Input 
2 2
0010
0100
Output 
5
Input 
3 4
001000
000010
000010
Output 
12
Input 
4 3
01110
01110
01110
01110
Output 
18

输入样例 复制 

2 2
0010
0100

输出样例 复制 

5

数据范围与提示

在第一个例子中，Sagheer会去一楼的1号房间，然后他会使用左右楼梯去二楼的2号房间。

在第二个例子中，他会去一楼的第四个房间，走右边的楼梯，然后去二楼的第四个房间，再走右边的楼梯，然后去最后一层的第二个房间。

在第三个例子中，他将在每层左右楼梯之间交替穿过整个走廊。

分类标签