翻硬币

题目 翻硬币

思路分析

给定初始状态 以及一些操作 询问最少多少次操作能变成目标状态

这类模型一般有两种写法

  宽搜（每个状态看做一个点 通过某种操作使得状态1变成状态2 就在他们之间连一条边 最后其实就是一个求最短距离的问题）但适合数据范围较小的问题

  尝试递推出每个开关应该继续的操作

也就是说 第一个状态只有第一个能确定（比对答案状态）

而一旦确定第一个状态 后面都不能改变前面的状态 只能对后面的连续开关做操作

每次前一个状态都能确定后一个状态如何

并没有选择性（看起来有多种选择性 实际上要是有解的话 就必然只有一个解）

代码实现

#include<bits/stdc++.h>
using namespace std;

string source,aim;

void turn(int i){
    if(source[i]=='*')
        source[i]='o';
    else
        source[i]='*';
}

int main()
{
    cin>>source>>aim;
    int res=0;
    for(int i=0;i+1<source.size();i++){
        if(source[i]!=aim[i]){
            turn(i),turn(i+1);
            res++;
        }
    }
    cout<<res<<endl;
    return 0;
}

同类题型

视频讲解

⬅️ 简单斐波那契(递推实现) 🏠 00-刷题理模型 ➡️ 费解的开关