- 总时间限制:
- 1000ms
- 内存限制:
- 1024kB
- 描述
-
有一种特殊的二进制密码锁，由n个相连的按钮组成（n<30），按钮有凹/凸两种状态，用手按按钮会改变其状态。
然而让人头疼的是，当你按一个按钮时，跟它相邻的两个按钮状态也会反转。当然，如果你按的是最左或者最右边的按钮，该按钮只会影响到跟它相邻的一个按钮。
当前密码锁状态已知，需要解决的问题是，你至少需要按多少次按钮，才能将密码锁转变为所期望的目标状态。
- 输入
- 两行，给出两个由0、1组成的等长字符串，表示当前/目标密码锁状态，其中0代表凹，1代表凸。
- 输出
- 至少需要进行的按按钮操作次数，如果无法实现转变，则输出impossible。
- 样例输入
-
011 000
- 样例输出
-
1
my version://AC #include<cstdio> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<string> #include<map> #include<cstring> #define DEBUG(x) cout << #x << " = " << x << endl using namespace std; char src[35],tar[35],t[35]; #define INF 0x3f3f3f3f inline void flip(char* c) { *c=*c=='0'?'1':'0'; } int main() { freopen("in.txt","r",stdin); scanf("%s",src); scanf("%s",tar); int N=strlen(src); int minTimes=INF; for(int p=0; p<2; p++) { strcpy(t,src); int d=p; int times=0; for(int i=0; i<N; i++) { if(d) { times++; flip(t+i); if(i>0) flip(t+i-1); if(i<N-1) flip(t+i+1); } if(t[i]==tar[i]) d=0; else d=1; } // DEBUG(times); // printf("%s ",t); if(strcmp(t,tar)==0) minTimes=min(minTimes,times); } if(minTimes!=INF) printf("%d ",minTimes); else printf("impossible "); return 0; }
perfect version:
/* bl8469 特殊密码锁 By Guo Wei */ #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> using namespace std; //枚举第一个按钮是否按下的两种情况即可。对于指定的一种情况，后面的事情都是确定的 int oriLock; int lock; int destLock; inline void SetBit(int & n,int i,int v) { if(v) n |= (1 << i); else n &= ~(1 << i); } inline void FlipBit(int & n,int i) { n ^= (1 << i); } inline int GetBit(int n,int i) { return (n >> i) & 1; } int main() { char line[40]; destLock = lock = oriLock = 0; cin >> line; int N = strlen(line); for(int i = 0; i < N; ++i) SetBit(oriLock,i, line[i] - '0'); cin >> line; for(int i = 0; line[i]; ++i) SetBit(destLock,i, line[i] - '0'); int minTimes = 1 << 30; for(int p = 0; p < 2; ++p) { //p代表最左边按钮 lock = oriLock; int times = 0; int curButton = p; for(int i = 0; i < N; ++i) { if(curButton) { ++ times; if( i > 0) FlipBit(lock,i-1); FlipBit(lock,i); if( i < N-1) FlipBit(lock,i+1); } if( GetBit(lock,i) != GetBit(destLock,i)) curButton = 1; else curButton = 0; } if( lock == destLock) minTimes = min(minTimes ,times); } if( minTimes == 1 << 30) cout << "impossible" << endl; else cout << minTimes << endl; return 0; }