001:特殊密码锁

011
000

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

void SetBit(int &c, int i, int v)
{
    if (v)
    {
        c |= (1<<i);
    }
    else
        c &= ~(1<<i);
}

/* 将开关转换为实际掩码
 */
int act2mask(int act, int n)
{
    int result = 0;
    for (int i=0; i<n; i++)
    {
        if (act&(1<<i))
        {
            result ^= (1<<i);
            if (i>0)
                result ^= (1<<(i-1));
            if (i<n-1)
                result ^= (1<<(i+1));
        }
    }
    return result;
}

/* change:
   返回按钮个数
   参数：
     from: 原锁
     to: 变化后的锁
     act: 最后两位
     n: 总位数

   注意：运算符的优先级
*/
int change(int from, int to, int act, int n)
{
    int count=0;
    if (((from^act2mask(act,n))&1) != (to&1))
        return -1;
    for (int i=1;i<n-1;i++)
    {
        SetBit(act, i+1, ((from^act2mask(act,n)^to)>>i)&1);
    }
    if ((from^act2mask(act,n))==to)
    {
        for (int i=0;i<n;i++)
            if (act&(1<<i))
                count++;
        return count;
    }
    else
        return -1;
}

int main()
{
    char a[32], b[32];
    int from=0, to=0, n;
    int found = 0;

    scanf("%s%s", a, b);
    n=strlen(a);
    for (int i=0;i<n;i++)
    {
        from = from * 2 + a[i]-'0';
        to = to * 2 + b[i]-'0';
    }

    for (int i=0;i<3; i++)
    {
        int count;
        if ((count=change(from, to, i, n))>=0)
        {
            printf("%d\n", count);
            found = 1;
            break;
        }
    }
    if (!found)
        printf("impossible\n");

    return 0;
}