思路:直接用优先队列优化bfs。

#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<string>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define Maxn 100010
#define inf 1<<30
using namespace std;
map<int,int> g;
int ans,n,ha[],Exp[];
char s[];
int tar;
struct QT{
int val,st;
int operator <(const QT &temp) const{
return st>temp.st;
}
};
priority_queue<QT> q;
int bfs(int temp)
{
int i,j,str;
while(!q.empty()) q.pop();
QT tt,p;
tt.val=temp,tt.st=;
q.push(tt);
while(!q.empty()){
p=q.top();
q.pop();
str=p.val;
if(str==tar) return p.st;
int a,b;
a=str/Exp[n-];
b=str%Exp[n-]/Exp[n-];
temp=b*Exp[n-]+a*Exp[n-]+str%Exp[n-];
if(!g[temp]){
tt.val=temp,tt.st=p.st+;
q.push(tt);
g[temp]=;
}
temp=str%Exp[n-]*+str/Exp[n-];
if(!g[temp]){
tt.val=temp,tt.st=p.st+;
q.push(tt);
g[temp]=;
}
}
}
int main()
{
char str[];
int i,j;
ha['A']=;
ha['G']=;
ha['C']=;
ha['T']=;
Exp[]=;
for(int i=;i<;i++)
Exp[i]=Exp[i-]*;
while(scanf("%d",&n)!=EOF){
ans=inf;
g.clear();
scanf("%s%s",str,s);
tar=;
int temp=;
for(i=;i<n;i++){
tar=tar*+ha[s[i]];
temp=temp*+ha[str[i]];
}
printf("%d\n",bfs(temp));
}
return ;
}

最新文章

  1. 架构之路(七)MVC点滴
  2. iOS-WKWebView携带cookie发送http请求,cookie失效
  3. 【转】 TCP协议中的三次握手和四次挥手(图解)
  4. Winform(C#.NET)自动更新组件的使用及部分功能实现(一点改进功能)
  5. UIScorlView 循环滚动
  6. 转载 SharePoint 2013配置Master Page and Page Layout
  7. form表单中的 action=./?&gt; 是什么意思
  8. Js 数组(一):基础应用
  9. SpringBoot2.0 项目异常日志,但不影响运行(待解决)
  10. mysql8.0.13修改密码
  11. 《机器学习实战》之一:knn(python代码)
  12. hdu 5877 Weak Pair (Treap)
  13. 第26月第18天 mybatis_spring_mvc
  14. 背水一战 Windows 10 (90) - 文件系统: 获取 Package 中的文件, 可移动存储中的文件操作, “库”管理
  15. packetfence 7.2网络准入部署(二)
  16. 不能往Windows Server 2008 R2 Server中复制文件的解决方法
  17. react-redux 的使用
  18. 写一写关于python开发面试的常遇到的问题以及解答吧,持续更新——看心情
  19. 2018.11.17 bzoj4259: 残缺的字符串(fft)
  20. [转帖] sparkdev 的 博客 systemd

热门文章

  1. Dijkstra&amp;&amp;Floyd
  2. MySQL备份工具percona-xtrabackup安装
  3. ubuntu18.04.1LTS系统远程工具secureCRT
  4. 子查询,用户管理,pymysql使用
  5. Python 中关于文件操作的注意事项
  6. openwrt(三) 固件的烧录
  7. python——标准异常总结
  8. python基础之面向对象编程介绍、类和对象
  9. MVN settings.xml
  10. ThinkPad 触控板双指不可以滑动