翻转（寒假每日一题+思维训练）

题目

小蓝用黑白棋的?n个棋子排成了一行，他在脑海里想象出了一个长度为?n的?01?串?T，他发现如果把黑棋当做?1，白棋当做?0，这一行棋子也是一个长度为?n?的?01?串?S。小蓝决定，如果在?S中发现一个棋子和它两边的棋子都不一样，就可以将其翻转变成另一个颜色。也就是说，如果?S?中存在子串?101 或者?010，就可以选择将其分别变为?111 和?000，这样的操作可以无限重复。小蓝想知道最少翻转多少次可以把?S?变成和?T?一模一样。

输入格式

输入包含多组数据。

输入的第一行包含一个正整数?D?表示数据组数。

后面?2D?行每行包含一个?01?串，每两行为一组数据，第?2i?1?行为第?i?组数据的?Ti，第?2i?行为第?i?组数据的?Si，Si?和?Ti?长度均为?ni。

输出格式

对于每组数据，输出一行包含一个整数，表示答案，如果答案不存在请输出??1。

数据范围

样例

输入样例

2
1000111
1010101
01000
11000

输出样例

2
-1

题目思路

? ? ? ? 该代码重要在与对思维的锻炼和对题目的分析。根据题目给出的规则和例子，我们可以轻易推出，改变数字中的一位数不会对另一位造成影响，因此我们只要从左到右或者从右向左遍历一遍，将s中与t中的不同修改，如果发现不能修改便返回-1。

源代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e6+10;

int n;
char t[N],s[N];

int main()
{
    scanf("%d",&n);
    while(n--){

        scanf("%s%s",t,s);
        
        int m=strlen(t);
        int ans=0;
        
        if(s[0]!=t[0]||s[m-1]!=t[m-1]) printf("%d\n",-1);
        else{
            for(int i=m-2;i>0;i--){
                if(s[i]!=t[i]){
                    if(s[i-1]==s[i+1] && s[i-1]!=s[i] && s[i-1]==t[i-1]) ans++;
                    else{
                        ans=-1;
                        break;
                    }
                }
            }
            
            printf("%d\n",ans);
        }
    }
    return 0;
}

?