POJ8469 特殊密码锁

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

描述
有一种特殊的二进制密码锁，由n个相连的按钮组成（n<30），按钮有凹/凸两种状态，用手按按钮会改变其状态。
然而让人头疼的是，当你按一个按钮时，跟它相邻的两个按钮状态也会反转。当然，如果你按的是最左或者最右边的按钮，该按钮只会影响到跟它相邻的一个按钮。
当前密码锁状态已知，需要解决的问题是，你至少需要按多少次按钮，才能将密码锁转变为所期望的目标状态。
输入
两行，给出两个由0、1组成的等长字符串，表示当前/目标密码锁状态，其中0代表凹，1代表凸。
输出
至少需要进行的按按钮操作次数，如果无法实现转变，则输出impossible。
样例输入

样例输出

解题思路：

由于第一个按钮是否按下会影响后面所有的按钮，因此枚举第一个按钮对应的两种情况。另外，如果按钮按下后和目标状态不相同，之前的情况已经枚举完毕，只需要按下下一个按钮即可。

代码：

#include <iostream>

#include <cstring>

using namespace std;

int len = ;

int result =  << ;//最终的结果

int cnt = ;//每次枚举得出的操作次数

//将第i位反转

void ReNum(char* a, int i) {

    if (a[i] == '')

    {

        a[i] = '';

    }

    else

    {

        a[i] = '';

    }

}

//比较是否相同

int cmp(char* a, char* b) {

    int i = ;

    for (; i < len; i++) {

        if (a[i] != b[i]) {

            return false;

        }

    }

    return true;

}

//设置反转

void Reversal(char* a, int i) {

    ReNum(a, i);

    if (i == ) {

        ReNum(a, i + );

    }

    else {

        ReNum(a, i - );

        ReNum(a, i + );

    }

    cnt++;

}

//获取更小的

int min(int i, int j) {

    if (i < j)

        return i;

    else

        return j;

}

int main()

{

    char a[];

    char target[]; //初始状态和目标状态

    char temp[];

    cin >> a >> target;

    len = strlen(a);

    if (cmp(a, target))//已经和目标状态相等

    {

        cout << ;

        return ;

    }

    for (int k = ; k < ; k++) //第一位反转与否

    {

        cnt = ;//记录置零

        memcpy(temp, a, len);

        if (k == )//改变第一位

        {

            Reversal(temp, );

            if (cmp(temp, target))//如果这样就可以了，这个肯定是最小值

            {

                result = min(result, cnt);//保存结果

            }

        }

        for (int i = ; i < len - ; i++)

        {

            if (temp[i] != target[i])

            {

                Reversal(temp, i + );//如果不相等就改变下一位

                if (cmp(temp, target))

                {

                    result = min(result, cnt);//保存结果

                }

            }

        }

    }

    if (result ==  << ) //如果没有成功过

        cout << "impossible";

    else

        cout << result;

    return ;

}

巴特西

POJ8469 特殊密码锁

最新文章

热门文章