特殊密码锁 问题描述：
有一种特殊的二进制密码锁，由n个相连的按钮组成（n<30），按钮有凹/凸两种状态，用手按按钮会改变其状态。
【POJ 8496 特殊密码锁】然而让人头疼的是，当你按一个按钮时，跟它相邻的两个按钮状态也会反转。当然，如果你按的是最左或者最右边的按钮，该按钮只会影响到跟它相邻的一个按钮。
当前密码锁状态已知，需要解决的问题是，你至少需要按多少次按钮，才能将密码锁转变为所期望的目标状态。
输入
两行，给出两个由0、1组成的等长字符串，表示当前/目标密码锁状态，其中0代表凹，1代表凸。
输出
至少需要进行的按按钮操作次数，如果无法实现转变，则输出impossible。
样例输入
011
000
样例输出
1
解题思路：本来还想从奇偶方面入手，但是发现自己想的太简单了，本来想根据0，1数量，从奇偶方面判断，后来试一试才发现，情况根本没那么简单。百度了一下，才知道贪心算法。先保证最后一位前面的数字都相同，不停按下按钮，如果到最后，最后一位也相同，则输出按下按钮的次数，否则输出Impossible。需要注意的一点就是，在前两个按钮不同的时候，是按第一个按钮，还是按第二个按钮，这个问题需要加以判断，若两种都可行，则最后需要输出按下次数最小的数值。
import java.util.Arrays;
import java.util.Scanner;
public class SpecialCodedLock {public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
char[] s = in.nextLine().toCharArray();
char[] goal = in.nextLine().toCharArray();
int count = 0;
int count_2 = 0;
int result = -1;
//第一种情况:前两个按钮不同，按下第二个按钮
char[] temp = Arrays.copyOf(s, s.length);
for(int i = 1;
i < goal.length;
i++) {
if(temp[i - 1] != goal[i - 1]) {
push(temp, i);
count++;
}
}//判断字符数组s与goal的最后一个字符是否相等
if(temp[temp.length - 1] == goal[goal.length - 1]) {
result = 1;
}
else {
count = (int) 1e9;
}temp = Arrays.copyOf(s, s.length);
//第二种情况：前两个按钮不同，按下第一个按钮
if(temp[0] != goal[0]) {
temp[0] = temp[0] == '0' ? '1' : '0';
if(1 < s.length)
temp[1] = temp[1] == '0' ? '1' : '0';
count_2++;
}for(int i = 2;
i < goal.length;
i++) {
if(temp[i - 1] != goal[i - 1]) {
push(temp, i);
count_2++;
}
}if(temp[temp.length - 1] == goal[goal.length - 1]) {
result = 1;
}
else {
count_2 = (int) 1e9;
}//如果result等于-1，则无法转变为目标字符串
if(result != -1) {
System.out.println(count > count_2 ? count_2 : count);
}
else {
System.out.println("impossible");
}
}//改变按下按钮的前后及自身的值
public static void push(char[] temp, int i) {
temp[i] = temp[i] == '0' ? '1' : '0';
temp[i - 1] = temp[i - 1] == '0' ? '1' : '0';
if(i + 1 < temp.length)
temp[i + 1] = temp[i + 1] == '0' ? '1' : '0';
}
}推荐阅读
- POJ 1364 King 差分约束系统
- POJ|POJ2728 Desert King
- POJ|POJ 1364 King 差分约束系统 SPFA
- POJ|POJ 2241 The Tower of Babylon 笔记