可以证明,无法将同一个字符翻转两次。所以从左到右依次按规则修改不相同的字符就可以。
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
using namespace std;
int D;
void roll(string s, string t) {
int len = (int)s.size();
//首尾有数字不同则直接输出-1
if (s[0] != t[0] || s[len - 1] != t[len - 1]) {
cout << -1 << endl;
return;
}
//以下,s,t首尾相同
//首先考虑len<3的情况
if (len < 3) {
//由于首尾相同,所以一定有s==t
cout << 0 << endl;
return;
}
//以下,len>=3且首尾相同
int step = 0;
for (int i = 1; i <= len - 2; i++) {
if (s[i] != t[i]) {
//只有i处前后都对应相等才行
if (s[i]!=s[i-1]&&s[i]!=s[i+1]) {
step++;
s[i] = t[i];
}
else {
cout << -1 << endl;
return;
}
}
}
//退出循环时,s==t
cout << step << endl;
}
int main() {
cin >> D;
string s, t;
for (int i = 0; i < D; i++) {
cin >> t;
cin >> s;
roll(s, t);
}
return 0;
}