首页 > 代码库 > 特殊密码锁
特殊密码锁
- 总时间限制:
- 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); } }
特殊密码锁
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。