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