codeforces 812 B Sagheer, the Hausmeister(枚舉)

題意：

有n層樓,小明需要從一層樓的左邊開始去關n層樓種還未關燈的房間的燈，其中一層中最左邊和最右邊都是樓梯,問小明關完所有燈的時間，不需要計算傳回的時間

解題思路：

小明到達一層樓隻有從左邊和右邊樓梯上來兩種情況，離開也一樣，是以一旦确定目前這一層樓小明是從哪邊上來，要從哪邊離開，那麼這層樓要怎麼走就已經确定下來了。這裡n隻有15，是以我們隻需要2^x(有燈亮的最頂層)去枚舉每一層樓的情況，最後算下答案，所有情況的答案取最小值就是最後的答案了。

代碼：

#include <bits/stdc++.h>

using namespace std;
int ord[22];
int a[23][105];
int l[105], r[105];
int ans, n, m;
void dfs(int x)
{
    int i, j;
    if(x>n)
    {
        int sum=0;
//        for(i=1; i<=n; i++)printf("%d", ord[i]);printf("\n");
        for(i=1; i<=n; i++)
        {
            if(i==n)
            {
                if(ord[i]==0)
                {
                    sum+=r[i]==0?-1:r[i];
                }
                else sum+=(l[i]==0)?-1:(m-1-l[i]);
                break;
            }
            if(ord[i]==0)
            {
                if(ord[i+1]==0)
                {
                    sum+=2*r[i];
                }
                else
                {
                    sum+=m-1;
                }
            }
            else
            {
                if(ord[i+1]==1)
                {
                    sum+=(l[i]==0)?0:(m-1-l[i])*2;
                }
                else
                {
                    sum+=m-1;
                }
            }

            sum++;
//            cout<<sum<<endl;
        }

        ans=sum<ans?sum:ans;
        return;
    }
    ord[x]=1;
    dfs(x+1);
    ord[x]=0;
    dfs(x+1);
    return;
}
int main()
{
    int i, j;

    cin>>n>>m;
    ans=n*m*4;
    m+=2;
    ord[1]=0;
    int s=n+1, num;
    for(i=n; i>=1; i--)
    {
        num=0;
        for(j=0; j<m; j++)
        {
            scanf("%1d", &a[i][j]);
            if(a[i][j])
            {
                r[i]=j;
                num++;
                if(!l[i])l[i]=j;
            }

        }
        if(num==0 && s==i+1)
        {
            s=i;
        }
    }
    n=s-1;
    dfs(2);
    printf("%d\n", ans);
    return 0;
}