有些人在离开工作场所时把灯开着，这是一种资源浪费。作为DHBW的管理员，Sagheer等到所有学生和教授离开大学建筑物，然后去关掉所有的灯。

建筑物由n层组成，左右两侧有楼梯。每层有m个沿着同一线的房间，房间之间有连接左右楼梯的走廊。换句话说，建筑物可以表示为一个有n行m + 2列的矩形，第一列和最后一列代表楼梯，中间的m列代表房间。

Sagheer站在左侧楼梯的底层。他希望关掉所有的灯，但在上楼之前不会离开所在楼层的房间。当然，Sagheer必须进入一个房间才能关掉灯。Sagheer通过楼梯上楼或者在同一楼层的相邻房间/楼梯间移动，每次移动到下一个楼层或相邻房间/楼梯间需要一分钟。在当前位置关掉房间里的灯不需要时间。帮助Sagheer找到关掉所有灯所需的最短总时间。

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

输入 第一行包含两个整数n和m（1 ≤ n ≤ 15和1 ≤ m ≤ 100）—楼层数和每层的房间数。

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

每个字符串的第一个和最后一个字符代表左侧和右侧楼梯，因此它们总是0。

输出 输出一个整数—关掉所有灯所需的最短总时间。

示例

1.Inputcopy
2 2
0010
0100
1.Outputcopy
5

2.Inputcopy
3 4
001000
000010
000010
2.Outputcopy
12

3.Inputcopy
4 3
01110
01110
01110
01110
3.Outputcopy
18

注意 在第一个示例中，Sagheer将前往底层的第1个房间，然后使用左侧或右侧楼梯前往第二层的第2个房间。

在第二个示例中，他将前往底层的第四个房间，使用右侧楼梯，前往第二层的第四个房间，再次使用右侧楼梯，然后前往最后一层的第二个房间。

在第三个示例中，他将穿过整个走廊，每层交替使用左侧和右侧楼梯。

CODE:

#include <bits/stdc++.h>
using namespace std;
int n,m,f[20][2][2],p;
char a[20][110];
int main()
{
	cin >> n >> m;
	m+=2;
	for (int i=n;i>=1;i--)
	{
		int x=0;
		for (int j=1;j<=m;j++) cin >> a[i][j],x+=a[i][j]-'0';
		if (!x) n--;
	}
	p=m+1;
	f[1][0][0]=m;
	while (--p>=1&&a[1][p]=='0') f[1][0][0]--;
	f[1][0][0]*=2;
	f[1][0][0]-=2;
	f[1][0][1]=m-1;
	f[1][1][0]=1e9;
	f[1][1][1]=1e9;
	for (int i=2;i<=n;i++)
	{
		p=m+1;
		f[i][0][0]=m;
		while (--p>=1&&a[i][p]=='0') f[i][0][0]--;
		if (i!=n) f[i][0][0]*=2,f[i][0][0]-=1;
		f[i][0][0]+=min(f[i-1][0][0],f[i-1][1][0]);
		f[i][0][1]=m+min(f[i-1][0][0],f[i-1][1][0]);
		p=0;
		f[i][1][1]=m;
		while (++p<=m&&a[i][p]=='0') f[i][1][1]--;
		if (i!=n) f[i][1][1]*=2,f[i][1][1]-=1;
		f[i][1][1]+=min(f[i-1][1][1],f[i-1][0][1]);
		f[i][1][0]=m+min(f[i-1][1][1],f[i-1][0][1]);
	}
	cout << min(f[n][0][0],min(f[n][0][1],min(f[n][1][0],f[n][1][1])));
	return 0;
}

若有疑问或主意，请 @ALANYQ