首页 > 代码库 > 特殊密码锁

特殊密码锁

总时间限制: 
1000ms
 
内存限制: 
1024kB
描述

有一种特殊的二进制密码锁,由n个相连的按钮组成(n<30),按钮有凹/凸两种状态,用手按按钮会改变其状态。

然而让人头疼的是,当你按一个按钮时,跟它相邻的两个按钮状态也会反转。当然,如果你按的是最左或者最右边的按钮,该按钮只会影响到跟它相邻的一个按钮。

当前密码锁状态已知,需要解决的问题是,你至少需要按多少次按钮,才能将密码锁转变为所期望的目标状态。

输入
两行,给出两个由0、1组成的等长字符串,表示当前/目标密码锁状态,其中0代表凹,1代表凸。
输出
至少需要进行的按按钮操作次数,如果无法实现转变,则输出impossible。
样例输入
011
000

样例输出 

1

分析

只需要考虑是否按下第一个灯。因为如果第一个灯的状态被确定了,那么是否按下第二个灯也就决定了(如果第一个灯与期望不同,则按下,如果期望相同,则不按下)同理,第三个灯是否按下也唯一确定。

所以,本题只要分两种情况:灯1被按下和没有被按下 
之后使用for循环判断别的灯是否需要按下即可 
当循环结束,若现在的灯况与答案相同,则输出两种方案中按键次数最少的,若不同,则impossible

代码

#include <cstdio>
#include <cstring>
char str[33];
char str1[33];
char str2[33];
int len;
char change(char s){
    if(s == 1)return 0;
    else return 1;
}
int resolve(int p){
    for(int i = 2;i <= len;i++){
        /*验证一下 str1的改变
        for(int j = 1;j <= len;j++)
            printf("%c",str1[j]);
        printf("\n");

        for(int j = 1;j <= len;j++)
            printf("%c",str2[j]);
        printf("\n");
        */
        if(str1[i-1] != str2[i-1]){
            p++;
            str1[i] = change(str1[i]);
            if(i != len)
            str1[i+1] = change(str1[i+1]);
        }
    }
    //printf("%c vs %c\n",str1[len],str2[len]);
    if(str1[len] != str2[len])return -1;    //最后一个字符不相等,说明无法转换为目标状态
    return p;
}
int main(){
    scanf("%s",str+1);
    scanf("%s",str2+1);
    len = strlen(str+1);
    for(int i = 1;i <= len;i++)
        str1[i] = str[i];
    //将第一个按钮按下
    str1[1] = change(str1[1]);
    str1[2] = change(str1[2]);
    int ans = resolve(1);
    //printf("ans:%d\n ",ans);
    //不按下第一个按钮
    for(int i = 1;i <= len;i++) //这里要用str重置str1,因为它已经被改变了
        str1[i] = str[i];
    int ans2 = resolve(0);
    //printf("ans2:%d\n ",ans2);
    if(ans == ans2 && ans == -1)printf("impossible");
    else{
        if(ans == -1 || ans2 == -1)
             printf("%d",ans > ans2 ? ans : ans2);
        else
             printf("%d",ans < ans2 ? ans : ans2);
    }
}

特殊密码锁