001: special password lock
Total time limit:
1000ms
Memory limit:
1024kB
describe
There is a special binary password lock, which is composed of N connected buttons (n < 30). The buttons have two states of concave / convex. Pressing the button by hand will change its state.
However, the headache is that when you press a button, the two adjacent buttons will reverse. Of course, if you press the leftmost or rightmost button, it will only affect the button next to it.
The current password lock state is known, and the problem to be solved is how many times you need to press the button to change the password lock to the desired target state.
input
Two lines, giving two equal length strings composed of 0 and 1, representing the current / target password lock state, where 0 represents concave and 1 represents convex.
output
Press the button at least times. If the transformation cannot be realized, the output is impossible.
sample input
011 000
sample output
1
Just press the first one on the left to enumerate by category, compare the times of the two schemes, and take the smaller output. Here, an integer addition operation is used to save the binary number. The following code is highly integrated. It's very brief. Actually, it can be written separately and more clearly
#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); // Set the i-th bit to 1 N? I + 1 or operation
else
n &= ~(1 << i); // Set the i-th bit to 0 N? I * 0 and operation
}
inline void FlipBit(int & n, int i)
{
n ^= (1 << i); // Invert bit i
}
inline int GetBit(int n, int i)
{
return (n >> i) & 1; // Use and 1 shift to extract the i-th digit
}
int main()
{
char line[40];
//oriLock is the original result, destLock is the target result, and an integer is used to represent the binary number
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;
// Press first position press and first position do not press to enumerate
for (int p = 0; p < 2; ++p) {
lock = oriLock;
int times = 0;
int curButton = p;
for (int i = 0; i < N; ++i) {
if (curButton) {
++times;
// Here's an integrated approach
// Left and right boundaries are considered
if (i > 0)
FlipBit(lock, i - 1);
// Flip this position
FlipBit(lock, i);
if (i < N - 1)
FlipBit(lock, i + 1);
}
// Flip as long as the current bits are different
if (GetBit(lock, i) != GetBit(destLock, i))
curButton = 1;
else
curButton = 0;
}
// Judge whether it is the same after turning all
if (lock == destLock)
minTimes = min(minTimes, times);
}
if (minTimes == 1 << 30)
cout << "impossible" << endl;
else
cout << minTimes << endl;
return 0;
}