翻转（蓝桥杯2023大学C组试题E）

【问题描述】：小蓝用黑白棋的n个棋子排成了一行，他在脑海里想象出了一个长度为n的01串T，他发现如果把黑棋当作1、白棋当做0，这一行棋子是一个长度为n的01串S。

      小蓝如果在S中发现一颗棋子和它两边的棋子都不一样，可以将其翻转变成另一个颜色。也就是说，如果S中存在子串101或者010，可以选择将其分别变为111和000，这样的操作可以无限重复。

     小蓝想知道最少翻转多少次可以把S变成和T一模一样。

     输入：输入包含多组数据。输入的第一行包含一个正整数D，表示数据的组数。后面2D行，每行包含一个01串，每两行为一组数据，第2i-1行为第i组数据的Ti(i)为下标，第2i行为第i组数据的Si(i为下标)，Si(i为下标)和Ti(i)为下标的长度均为ni（i为下标）。

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

【输入样例】

2

1000111

1010101

01000

11000

【输出样例】

2

-1

【试题解析】

       这是一道思维题。

      什么时候无解？如果第一颗或最后一颗棋子不同，无解。因为第一颗和最后一颗棋子不能翻转。

      每颗能翻动的棋子只能翻一次，因为翻过之后，它和相邻棋子一样不能再翻了。要使S和T最终一样，那么每颗不同的棋子都要翻一次。所以一种简单且正确的方法是从左到右枚举，从S的第2颗棋子开始，与T比较，如果不同，就尝试翻动。如果能翻成一样，就继续翻，如果不能翻成一样，就无解。

【参考程序如下】

#include <stdio.h>
#include <string.h>
using namespace std; 
char s[1000010],t[1000010];
int main(int argc, char** argv)
 {
	int D;
	scanf("%d",&D);
	while(D--)
	{
		scanf("%s",s + 1);
		scanf("%s",t + 1);
		int n = strlen(s + 1);
		if(s[1] != t[1] || s[n] != t[n]) {
       	puts("-1");
       	continue;}
	   int ans = 0;
	   for(int i = 2; i < n; i++)
	    if(s[i] != t[i])
		{
	    	if(t[i] != t[i - 1] && t[i] != t[i + 1])  //中间的棋子和两边不同 
	    	{
	    		t[i] = t[i + 1];
	    		ans++;
			}
		else
		{
			ans = -1;
			break;
		}
		
	   printf("%d\n",ans);
	}
	return 0;
  }
}