题目链接：

题意：n层楼，每层有m个房间，左右两边是楼梯，输入一个n*（m+2）的字符串，字符1代表这个房间灯亮。要想关闭上层的等，低层的灯必须全部关闭。现在问你关闭所有的灯最少移动多少次。

分析：动态规划或者dfs都可以。dp[i][0]代表到达第i层的左边楼梯最短移动，dp[i][1]代表到达第i层的右边楼梯的最短移动。初始化dp[1][0]=0,dp[1][1]=m+1;

　　　　dp[i][0]=min(dp[i-1][0]+r[i-1]*2,dp[i-1][1]+m+1)+1;

　　　　dp[i][1]=min(dp[i-1][1]+(m+1-l[i-1])*2,dp[i-1][0]+m+1)+1;

　　　　然后dp递推到需要关灯的最高层即可（如果那一层以上再没有需要关的灯即为最高层）。最高层的移动不需要再回来，只需要关灯就行。

AC代码：

1 #include
      
        2 using namespace std; 3  4 char a[20][105]; 5 int l[20],r[20]; 6 int dp[20][2]; 7 int main() { 8     ios_base::sync_with_stdio(0); 9     cin.tie(0);10     int n,m;11     memset(a,'0',sizeof(a));12     memset(l,0,sizeof(l));13     memset(r,0,sizeof(r));14     memset(dp,0,sizeof(0));15     cin>>n>>m;16     for(int i=n;i>=1;i--){17         for(int j=0;j<=m+1;j++){18             cin>>a[i][j];19             if(a[i][j]=='1'){20                 r[i]=j;21                 if(l[i]==0){22                     l[i]=j;23                 }24             }25         }26     }27     int high=n;28     for(int i=n;i>0;i--){29         if(l[i]==0&&r[i]==0){30             high--;31         }32         else break;33     }34     dp[1][0]=0;35     dp[1][1]=m+1;36     for(int i=2;i<=high;i++){37         if(l[i-1]==0&&r[i-1]==0){38             dp[i][0]=min(dp[i-1][0],dp[i-1][1]+m+1)+1;39             dp[i][1]=min(dp[i-1][1],dp[i-1][0]+m+1)+1;40         }41         else {42             dp[i][0]=min(dp[i-1][0]+r[i-1]*2,dp[i-1][1]+m+1)+1;43             dp[i][1]=min(dp[i-1][1]+(m+1-l[i-1])*2,dp[i-1][0]+m+1)+1;44         }45     }46     int result;47     result=min(dp[high][0]+r[high],dp[high][1]+(m+1-l[high]));48     cout<
       
        <