POJ-8469 特殊密码锁

2019-11-14 09:36:33

字体：大中小

来源：转载

供稿：网友

题目来源限制描述输入输出样例输入样例输出解题报告思路分析源代码

题目

来源

中国MOOC网，程序设计与算法（二）第一周作业1 http://cxsjsxmooc.openjudge.cn/2017t2sPRinghw1/1/

限制

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

描述

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

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

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

输入

两行，给出两个由0、1组成的等长字符串，表示当前/目标密码锁状态，其中0代表凹，1代表凸。

输出

至少需要进行的按按钮操作次数，如果无法实现转变，则输出impossible。

样例输入

011 000

样例输出

解题报告

思路分析

首先思考枚举法，每个按钮有2种状态，但是最多可能有30个灯，因此状态有2^30之多，穷举一定会超时。

重点1 一个灯如果按了第二下，就会抵消上一次按下所产生的影响。因此，一个灯只有按或者不按两种情况，不存在一个灯要开关多次的情况。

例如八个灯 00000000 按1后 11000000 按3后 10110000 按1后 01110000 这和八个灯 00000000 只按一次3后 01110000 是完全相同的情况

重点2 我们只需要考虑是否按下第一个灯。因为如果第一个灯的状态被确定了，那么是否按下第二个灯也就决定了（如果第一个灯与期望不同，则按下，如果期望相同，则不按下）同理，第三个灯是否按下也唯一确定。

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

源代码

很乱，我写了一个Push函数专门负责改变灯的状态，这里主要是要注意边界条件（pos为0和len-1）同时，为了方便转换，我在进入函数之前，将char类型的元素-48变为了int型，这样1-0=1，1-1=0方便转换，在函数结束时，将元素+48重新转换为char类型方便使用strcmp函数进行判断

#include <stdio.h>#include <string.h>char s[35] = {0};char s2[35] = {0};int len = 0;char e[35]={0};void Push( int pos, char led[] );int main(){ //这两个f是干嘛的，我写的时候应该知道，但是现在只有上帝知道 int f1 = 0; int f2 = 0; int i = 0; int r1 = 0; int r2 = 0; scanf("%s",s); len = strlen(s); for( i=0;i<len;i++) s2[i] = s[i]; s2[i] = '/0'; scanf("%s",e); r1 = 1; Push(0,s); for( i = 1 ; i < len ; i ++ ) { if( s[i-1] != e[i-1] ) { Push(i,s); r1++; } } if(strcmp(s,e)!=0) f1=1; r2 = 0; for( i = 1 ; i < len ; i ++ ) { if( s2[i-1] != e[i-1] ) { Push(i,s2); r2++; } } if(strcmp(s2,e)!=0) f2=1; if( f1 == 1 && f2 == 1 ) { printf("impossible"); return 0; } if( f1 == 1 && f2 == 0 ) { printf("%d",r2); return 0; } if( f1 == 0 && f2 == 1 ) { printf("%d",r1); return 0; } if( r1 < r2 ) printf("%d",r1); else printf("%d",r2); return 0;}void Push( int pos, char led[] ){ if(pos>0) led[ pos - 1 ]-=48; led[pos]-=48; if(pos<len-1) led[ pos + 1 ]-=48; if( pos == 0 ) { led[pos] = 1 - led[pos]; led[ pos + 1 ] = 1 - led[ pos + 1 ]; } else if( pos == len-1 ) { led[ len-1 ] = 1 - led[len-1]; led[ len - 2 ] = 1 - led[ len - 2 ]; } if( pos > 0 && pos < len-1 ) { led[pos] = 1 - led[pos]; led[ pos + 1 ] = 1 - led[ pos + 1 ]; led[ pos - 1 ] = 1 - led[ pos - 1 ]; } if(pos>0) led[ pos - 1 ]+=48; led[pos]+=48; if(pos<len-1) led[ pos + 1 ]+=48;}/* * ┏┓　　　┏┓ *┏┛┻━━━┛┻┓ *┃　　　　　　　┃ 　 *┃　　　━　　　┃ *┃　┳┛　┗┳　┃ *┃　　　　　　　┃ *┃　　　┻　　　┃ *┃　　　　　　　┃ *┗━┓　　　┏━┛ *　　┃　　　┃神兽保佑 *　　┃　　　┃代码无BUG！ *　　┃　　　┗━━━┓ *　　┃　　　　　　　┣┓ *　　┃　　　　　　　┏┛ *　　┗┓┓┏━┳┓┏┛ *　　　┃┫┫　┃┫┫ *　　　┗┻┛　┗┻┛ *　　　 */

上一篇：图的两种表示和接口

下一篇：1034.Head of a Gang (30)