Problem 2151. -- 关灯

2151: 关灯

Time Limit: 1 Sec  Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 159  Accepted: 22
[Submit][Status][Web Board]

Description

有些人离开教室时,不关灯,浪费电。LGDdp等所有的学生和老师离开教学楼后,把所有的灯关掉。
该建筑由n层。每层楼有m间房间,最左、最右有楼梯。换句话说,建筑物可以表示为一个有n行m + 2列的矩形,第一列和最后一列代表楼梯,而中间的m列代表房间。
LGDdp站在第一层的左边楼梯。他想把所有的灯都关掉。他所站的这层上的所有灯都熄灭后,他才能再上楼。LGDdp需要一分钟的时间使用楼梯去下一个楼层,或者从当前的房间/楼梯移动到同一楼层的相邻房间/楼梯。关灯不花时间,移动花时间。LGDdp忙着刷题,机智的你能帮他找到关闭所有灯的最少时间吗?
请注意,LGDdp不必回到他的起始位置。

Input

第一行包含两个整数n和m(1≤n≤15和1≤m≤100) - 分别是每层的层数和房间数量。
接下来的n行包含建筑描述。每行包含长度为m + 2的二进制字符串,表示一个楼层(左侧楼梯,然后m个房间,然后右侧楼梯),其中0表示灯熄灭,1表示灯已亮。楼层从上到下排列,最后一行代表底层。
每个字符串的第一个和最后一个字符分别代表左边和右边的楼梯,所以它们总是0。

Output

一个整数 - 关闭所有灯光所需的最短总时间。

Sample Input

2 2
0010
0100
3 4
001000
000010
000010
4 3
01110
01110
01110
01110

Sample Output

5
12
18

HINT

在第一个例子中,LGDdp将进入底层的房间,然后他将使用左侧或右侧的楼梯进入二楼的房间。

在第二个例子中,他将去到底层的房间,使用右边的楼梯,去第二层的房间,再次使用右边的楼梯,然后去到最后一层的房间。

在第三个例子中,S型走位。

Author

wjw

[Submit][Status][Web Board]