首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。