[数据结构与算法]1208. 翻硬币 Java题解 【第四届蓝桥杯省赛C++B组】

?输入格式

两行等长的字符串，分别表示初始状态和要达到的目标状态。

输出格式

一个整数，表示最小操作步数

数据范围

输入字符串的长度均不超过100。
数据保证答案一定有解。

输入样例1：

**********
o****o****

输出样例1：

5

输入样例2：

*o**o***o***
*o***o**o***

输出样例2：

1

解题思路：

由于存在唯一解，并且每次翻硬币时，都会产生连锁反应，即如果不重复翻同一枚硬币，则只有唯一解，所以从左往右递推即可。

Java代码：

import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[] s1 = br.readLine().toCharArray();
		char[] s2 = br.readLine().toCharArray();
		
		int ans = 0;
		for(int i = 0; i < s1.length; i++) {
			if(s1[i] != s2[i]) {
				s1[i + 1] = (s1[i + 1] == '*') ? 'o' : '*';
				ans++;
			}
		}
		System.out.println(ans);
	}
}