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型走位。

新手，不晓得怎么看是不是最优解。

#include <stdio.h>
int main(void)
{
    int i,j,m,n,count=0,flag=1;    
    char a[15][102];
    scanf("%d%d",&n,&m);
    getchar();
    for(i=0;i<n;i++)
    {
        for(j=0;j<m+2;j++)
            scanf("%c",&a[i][j]);
        getchar();
    }
    for(i=n-1;i>0;i--)
    {
        if(flag>0)
        {
            for(j=m+1;j>=0;j--)
            {
                if(a[i][j]=='1')
                {
                    if(j>=m/2+1)
                    {
                        count+=(m+1);
                        flag*=-1;
                    }
                    else
                    {
                        count+=(2*j);
                    }
                    break;
                }
            }
        }
        else
        {
            for(j=0;j<m+2;j++)
            {
                if(a[i][j]=='1')
                {
                    if(j<m/2+1)
                    {
                        count+=(m+1);
                        flag*=-1;
                    }
                    else
                    {
                        count+=2*(m+1-j);
                    }
                    break;
                }
            }
        }
        count++;
    }
    if(flag>0)
    {
        for(j=m+1;j>=0;j--)
        {
            if(a[0][j]=='1')
            {
                count+=j;
                break;
            }
        }
    }
    else
        for(j=0;j<m+2;j++)
        {
            if(a[0][j]=='1')
            {
                count+=(m+1-j);
                break;
            }
        }
    printf("%d\n",count);
    return 0;
}

这个题目，有所谓的“最优解”吗？   满足题意的应该只有唯一解！

LGDdp站在第一层的左边楼梯。他想把所有的灯都关掉。他所站的这层上的所有灯都熄灭后，他才能再上楼。

所以对于每一层楼来说，只要判断离入口楼梯位（比如起始位（0,0））最远的那一盏需要灭掉的灯是在该层楼的左半边还是右半边，就可以知道应该从哪个楼梯口上去更高的一层。（比如楼主给出的例一的一层应该从左边上楼，例二例三的一层应该从右边上楼）也就知道了这一层需要花多少分钟时间；
以此类推：到了第二层，如果你在最左边的楼梯口就得找最右边的那盏灯；如果你在最右边的楼梯口就得找最左边的那盏灯；如果这一层没有灯，那就直接再上一层楼。……（）

值得注意的是，有些测试样例可能会出现100层的楼，可只有前三层有灯需要关，这时候你走完前三层就应该立刻停止计数，不能浪费体力往上爬楼了。。。不然结果就会是错误的了。


----------------------------------------------
【2018-2-17更新】我这个思路是错误的。正确的在楼下，请不要被误导。   这里不直接修改原答，是为了让后续对话不至于无厘头。请后来者注意。

[此贴子已经被作者于2018-2-17 00:28编辑过]

代码思路再捋捋。那你的代码测试了一下，给你一个“输出了错误结果”的样例
input
6 3（前两层空的应该直接上楼）
01110
01110
01110
01110
00000
00000
output
20(正确答案正是20)
input
6 3（四层以上是空的，不必再走）
00000
00000
01110
01110
01110
01110
ouput
21(正确答案应该是18)

[此贴子已经被作者于2018-2-14 23:36编辑过]

我思路是对的，不过确实没有考虑到顶楼已经关灯的情况。应该加一次查找最高没关灯的楼层。

#include <stdio.h>
int main(void)
{
    int i,j,m,n,p=0,count=0,flag=1,flag2=0;    
    char a[15][102];
    scanf("%d%d",&n,&m);
    getchar();
    for(i=0;i<n;i++)
    {
        for(j=0;j<m+2;j++)
            scanf("%c",&a[i][j]);
        getchar();
    }
    for(i=0;i<n;i++)
    {
        for(j=0;j<m+2;j++)
            if(a[i][j]=='1')
            {
                flag2=1;
                break;
            }
        if(flag2)
            break;
        p++;
    }
    for(i=n-1;i>p;i--)
    {
        if(flag>0)
        {
            for(j=m+1;j>=0;j--)
            {
                if(a[i][j]=='1')
                {
                    if(j>=m/2+1)
                    {
                        count+=(m+1);
                        flag*=-1;
                    }
                    else
                    {
                        count+=(2*j);
                    }
                    break;
                }
            }
        }
        else
        {
            for(j=0;j<m+2;j++)
            {
                if(a[i][j]=='1')
                {
                    if(j<m/2+1)
                    {
                        count+=(m+1);
                        flag*=-1;
                    }
                    else
                    {
                        count+=2*(m+1-j);
                    }
                    break;
                }
            }
        }
        count++;
    }
    if(flag>0)
    {
        for(j=m+1;j>=0;j--)
        {
            if(a[0][j]=='1')
            {
                count+=j;
                break;
            }
        }
    }
    else
        for(j=0;j<m+2;j++)
        {
            if(a[p][j]=='1')
            {
                count+=(m+1-j);
                break;
            }
        }
    printf("%d\n",count);
    return 0;
}

起初语文不好看了几下不理解题意就逃了,然后看过这解释后就知道题目在说啥了~

理解后感觉这个方法不准~单靠判断楼梯距离是有漏洞的~

其实这题还是存在最优解的~

应该分两条路径综合判断~
第一条是关掉最左边的灯所用的最小步数s1
第二条是关掉最右边的灯所用的最小步数s2

然后由上一层的s1,s2递推下一层所用的最小步数的新的s1,s2

最后得出结果
这样可以确保是最优解~

PS:所以保留数据直接保留最左边的灯和最右边的灯中间的直接忽略就行了~

[此贴子已经被作者于2018-2-15 23:12编辑过]

你可能还是有一点没理解到位。。。

就是从第一层起，我们必须先关完该层所有灯才能上楼。所以我们要先搞清楚自己是站在最左边的楼梯口还是最右边的楼梯口，然后看一下需要关闭的离自己最远的那一盏灯是在这栋楼的中轴线的哪半边。如果是离自己近的这边，那就意味着我只需要走到那最远的一盏灯，然后立即返回起始楼梯口  上楼。如果是离自己远的那边，那就意味着我们需要遍历这一层，然后从对面那个楼梯口  上楼

1.确实我们只需要关注每一层离自己所在楼梯口最远的那一盏灯，就可以计算出这一层需要走多少步。
2.如果某层我们已知离自己所在楼梯口最远的那盏灯正好处在这栋楼的正中央（左右房间数相等）；这时候我们就会出现两条等长的路径通往更高层，而你从哪一个楼梯口到达更高层又会影响到那一层计算步数。所以我们需要根据更高层的最远灯位置来判断这一层是应该从左边的楼梯口上去还是右边的

综上所述：我觉得处理这个问题关键参数只有：1每层拥有的房间数。2每层最左和最右的房间下标。

不多说什么,就是看看这个案例是不是像你说的那样~

0000100
1000000

这个不就是很明显关掉第一层的灯后兜回左侧的楼梯么,那就显然要根据下一层才能判断该走哪个楼梯了吧~

根据题意，最左最右应该还有一个楼梯口，这个位置没有灯需要关；楼层从上到下排列，最后一行代表底层。   我调整测试案例为

010000000
*00001000

*为题目所说的出发结点。
按照我之前的说法，应该是往右走到路的尽头，然后上楼，再走到最左边这盏灯的位置，累计需要7+1+1+7=16步
而按照@九转星河 的说法，在到达1层的最右一盏灯（5步）的时候分别统计：从它出发经左楼梯口到达2层最右灯的路径长度（5+1+1）；从它出发经右楼梯口到达2层最左灯的路径长度（3+1+7）。相权取其轻，累计只需要5+（5+1+1）=12步

@九转星河 在六楼的思路才是正确的。