藍橋杯翻硬幣問題
- 題目
- 思路
- 1.指標寫的
- 2.string寫的
題目
問題描述
小明正在玩一個“翻硬幣”的游戲，
桌上放著排成一排的若干硬幣，我們用 * 表示正面，用 o 表示反面（是小寫字母，不是零），
比如，可能情形是：oo*oooo
如果同時翻轉左邊的兩個硬幣，則變為：oooo***oooo
現在小明的問題是：如果已知了初始狀態和要達到的目標狀態，每次只能同時翻轉相鄰的兩個硬幣,那么對特定的局面，最少要翻動多少次呢？
我們約定：把翻動相鄰的兩個硬幣叫做一步操作，那么要求：
輸入格式
兩行等長的字串，分別表示初始狀態和要達到的目標狀態，每行的長度<1000
輸出格式
一個整數，表示最小操作步數，
樣例輸入1
********** （ 只是為了適應格式）
o**** o****
樣例輸出1
5
思路
這道題呢說思路的話，我就是拿到題就直接寫了，沒有多想什么（但是我自己知道演算法的效率不怎么高），所以還請大神能在下面提供更好的思路（勿噴哈哈）
1.指標寫的
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<string.h>
using namespace std;
int dfs(int N, char *str, char * str2)
{
int count=0;
for(int i=0;i<N;i++){
if(str[i]==str2[i]){
continue;
}else
{
if(str[i]=='*'){
str[i]='o';
}else{
if(str[i]=='o')
str[i]='*';
}
if(str[i+1]=='*'){
str[i+1]='o';
}else{
if(str[i+1]=='o')
str[i+1]='*';
}
count++;
}
}
return count;
}
int main(){
char* str = (char*)malloc(100*sizeof(char));
char* str2 = (char*)malloc(100*sizeof(char));
cin>>str;
cin>>str2;
int num;
int N = strlen(str);
num=dfs(N,str,str2);
cout<<num;
return 0;
}
也可以用new，看你們想用啥了，
2.string寫的
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<string.h>
using namespace std;
int dfs(int N, string str, string str2)
{
int count=0;
for(int i=0;i<N;i++){
if(str[i]==str2[i]){
continue;
}else
{
if(str[i]=='*'){
str[i]='o';
}else{
if(str[i]=='o')
str[i]='*';
}
if(str[i+1]=='*'){
str[i+1]='o';
}else{
if(str[i+1]=='o')
str[i+1]='*';
}
count++;
}
}
return count;
}
int main(){
string str;
string str2;
cin>>str;
cin>>str2;
int num;
int N = str.size();
num=dfs(N,str,str2);
cout<<num;
return 0;
}
還是要加油啊，最近有點忙，自己很多的想法也沒實作，也沒有時間寫一些小專案，只能更新些不算厲害的演算法題了，加油！
想，就去做
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/278164.html
標籤：其他