Today Is a Rainy Day UVALive - 7263

本文主要是介绍Today Is a Rainy Day UVALive - 7263，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5275

给两个串s1 s2 有两种操作 一是把单个字符改变 二是吧一种字符改变 问最少几次操作将s2变为s1

第二种操作肯定是越多越好 预处理第二种操作各个状态与原始状态123456的距离 对每次查询 枚举所有状态 把s2按当前状态进行第二种操作后的得到的字符串与s1比较 看有几个不一样 再加上距离后取最小值

#include <bits/stdc++.h>
using namespace std;
const int maxm=1e6+10;
const int N=0x3f3f3f3f;map <string,int> mp;
queue <string> que;
string pre[maxm];
string s1,s2;
int n,tot;void init()
{string cur,tmp;int i,j,k;cur="000000",tmp="000000";que.push("123456");mp["123456"]=1;pre[++tot]="123456";while(!que.empty()){cur=que.front();que.pop();for(i=0;i<6;i++){for(j=0;j<6;j++){if(i==j) continue;for(k=0;k<6;k++){if(cur[k]=='1'+i) tmp[k]='1'+j;else tmp[k]=cur[k];}if(!mp[tmp]){que.push(tmp);mp[tmp]=mp[cur]+1;pre[++tot]=tmp;}}}}
}int solve()
{int res,cnt,i,j;res=N;for(i=1;i<=tot;i++){cnt=mp[pre[i]]-1;for(j=0;j<n;j++) if(pre[i][s1[j]-'0'-1]!=s2[j]) cnt++;res=min(res,cnt);}return res;
}int main()
{int i;init();while(cin>>s2>>s1){n=s2.size();printf("%d\n",solve());}return 0;
}

 

这篇关于Today Is a Rainy Day UVALive - 7263的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---