hust 1605 bfs

思路：直接用优先队列优化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[255],Exp[15];
char s[13];
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=0;
    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-1];
        b=str%Exp[n-1]/Exp[n-2];
        temp=b*Exp[n-1]+a*Exp[n-2]+str%Exp[n-2];
        if(!g[temp]){
            tt.val=temp,tt.st=p.st+1;
            q.push(tt);
            g[temp]=1;
        }
        temp=str%Exp[n-1]*5+str/Exp[n-1];
        if(!g[temp]){
            tt.val=temp,tt.st=p.st+1;
            q.push(tt);
            g[temp]=1;
        }
    }
}
int main()
{
    char str[13];
    int i,j;
    ha['A']=1;
    ha['G']=2;
    ha['C']=3;
    ha['T']=4;
    Exp[0]=1;
    for(int i=1;i<15;i++)
        Exp[i]=Exp[i-1]*5;
    while(scanf("%d",&n)!=EOF){
        ans=inf;
        g.clear();
        scanf("%s%s",str,s);
        tar=0;
        int temp=0;
        for(i=0;i<n;i++){
            tar=tar*5+ha[s[i]];
            temp=temp*5+ha[str[i]];
        }
        printf("%d
",bfs(temp));
    }
    return 0;
}