传送门
由于n只有15,因此可以枚举每一层是从左走还是从右走，而这一层是一直走到尽头还是走到最后一个再返回取决于上一层，预处理出每一层左右走到尽头的值，再根据枚举出的状态计算即可。总的时间复杂度是O(nn^15)
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
#define inf 1000000000LL
#define mod 1000000007
using namespace std;
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
char a[20][105];
int c[20][2];
int xu[20];
int main()
{
// while(true)
{
int n=read(),m=read()+2;
for(int i=0; i<n; i++) scanf("%s",a[i]);
int sta=0,flag=0;
for(int i=0; i<n; i++){
int p1=-1,p2=-1;
for(int j=0; j<m; j++){
if(a[i][j]=='1'){
if(p1==-1) p1=j;
p2=j;
}
}
if(p1==-1){
c[i][0]=c[i][1]=0;
if(!flag) sta++;
}else{
flag=1;
c[i][0]=p2;
c[i][1]=m-p1-1;
}
}
int cur,pre,sum,ans=inf;xu[n-1]=1;
for(int i=0; i<(1<<n-sta); i++){
sum=n-sta-1;
for(int j=n-2; j>=sta; j--){
xu[j]=(i>>j-sta)&1;
}
for(int j=n-1; j>=sta; j--){
if(j==sta){
sum+=c[j][xu[j]^1];
}
else{
if(xu[j-1]!=xu[j]) sum+=m-1;
else{
sum+=2*c[j][xu[j]^1];
}
}
}
ans=min(ans,sum);
}
if(sta==n) ans=0;
printf("%d\n",ans);
}
return 0;
}