首页 > 代码库 > hdu 魔板

hdu 魔板

#include <iostream>#include <cstring>#include <cstdio>#include <cstdlib>#include <cmath>#include <string>#include <vector>#include <list>#include <map>#include <queue>#include <stack>#include <bitset>#include <algorithm>#include <numeric>#include <functional>using namespace std;#define LL long long#define DB double#define N 100100#define esp 1e-6#define MOD 100003const int INF = 0x3f3f3f3f;const LL INFF = 1LL << 60;const DB EPS = 1e-9;const DB OO = 1e15;const DB PI = acos(-1.0);char s[10],e[10], str[10];int fac[] = {0,1,2,6,24,120,720,5040,40320};struct tt{    char a[20];    int hash;}u;int vis[N][2],num[N],coutt = 0;int kantuo(char s[]){    int ans = 0,temp,i,j;    for(i = 0 ; i < 8 ; i++)    {        temp = 0;        for(j = i+1; j < 8 ; j++)            if(s[i]>s[j]) temp++;        ans+=temp*fac[8-i-1];    }    return ans+1;}void bfs(){    char start[] = "12345678";    memset(vis,0,sizeof(vis));    int i,j,k,cur;    queue<tt>q;    strcpy(u.a,start);    u.hash = kantuo(start);    vis[u.hash][0] = N;    q.push(u);    while(!q.empty())    {        tt v = q.front();        q.pop();        //if(strcmp(v.a,e) == 0) return ;        for(i = 1 ; i <= 3 ; i++)        {            if(i == 1){                for(j = 7 ,k = 0; j >=0 ; j--) str[k++] = v.a[j];str[k] = \0;            }else if(i == 2)            {                str[0] = v.a[3];str[1] = v.a[0];str[2] = v.a[1];str[3] = v.a[2];                str[4] = v.a[5];str[5] = v.a[6];str[6] = v.a[7];str[7] = v.a[4];str[8] = \0;            }else {                str[0] = v.a[0];str[1] = v.a[6];str[2] = v.a[1];str[3] = v.a[3];                str[4] = v.a[4];str[5] = v.a[2];str[6] = v.a[5];str[7] = v.a[7];str[8] = \0;            }            cur = kantuo(str);            if(vis[cur][0]) continue;            vis[cur][0] = v.hash;            vis[cur][1] = i;            strcpy(u.a,str);            u.hash = cur;            q.push(u);        }    }}void solve(){    int i,k = 0;    char pos[10];    for(i = 0; i < 8 ; i++)        pos[s[i]-0] = i+1+0;    for(i = 0; i < 8 ; i++)        str[i] = pos[e[i]-0];    int ans = kantuo(str);    while(vis[ans][0]!=N)    {        //printf("ans = %d i = %d\n",ans,vis[ans][1]);        num[k++] = vis[ans][1];        ans = vis[ans][0];    }    for(i = k -1 ; i>=0 ; i--)        if(num[i] == 1) printf("A");        else if(num[i] == 2) printf("B");        else printf("C");        printf("\n");}int main(){    //freopen("out.txt","w",stdout);    bfs();    while(~scanf("%s",s))    {        scanf("%s",e);        solve();    }    return 0;}