首页 > 代码库 > UVALive 6665 Dragonâ??s Cruller --BFS,类八数码问题
UVALive 6665 Dragonâ??s Cruller --BFS,类八数码问题
题意大概就是八数码问题,只不过把空格的移动方式改变了:空格能够向前或向后移动一格或三格(循环的)。
分析:其实跟八数码问题差不多,用康托展开记录状态,bfs即可。
代码:
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <vector>#include <queue>#include <cstdlib>#define Mod 1000000007#define SMod 10007#define INint 2147483647#define LL (0x3f3f3f3f3f3f3f3f)*2#define ll long longusing namespace std;#define N 500007struct node{ ll cantor,cost; int pos; bool operator <(const node& a)const { return cost > a.cost; }}S,E;priority_queue<node> que;ll fact[11] = {1,1,2,6,24,120,720,5040,40320,362880,3628800};int dx[4] = {1,-1,3,-3};int a[11],b[11],Can[N][11],vis[N];ll ans,ch,cv;ll Cantor(int *a){ int i,j; ll cnt; ll res = 0; for(i=0;i<9;i++) { cnt = 0; for(j=i+1;j<9;j++) if(a[i] > a[j]) cnt++; res += cnt*fact[8-i]; } return res;}void getcantor(ll cantor,int *a){ for(int i=0;i<9;i++) Can[cantor][i] = a[i];}void geta(ll cantor){ for(int i=0;i<9;i++) a[i] = Can[cantor][i];}void bfs(){ while(!que.empty()) que.pop(); memset(vis,0,sizeof(vis)); int i,j; que.push(S); //vis[S.cantor] = 1; while(!que.empty()) { node tmp = que.top(); que.pop(); ll cantor = tmp.cantor; ll cost = tmp.cost; int pos = tmp.pos; if(vis[cantor]) continue; vis[cantor] = 1; if(cost >= ans) continue; if(cantor == E.cantor) { ans = min(ans,cost); break; } geta(cantor); for(int k=0;k<4;k++) { int v = (pos+dx[k]+9)%9; swap(a[v],a[pos]); ll newcantor = Cantor(a); if(vis[newcantor]) { swap(a[v],a[pos]); continue; } getcantor(newcantor,a); swap(a[v],a[pos]); node now; now.cantor = newcantor; now.pos = v; if(k < 2) now.cost = cost + ch; else now.cost = cost + cv; if(now.cost >= ans) continue; //vis[newcantor] = 1; que.push(now); } }}int main(){ int i,j; while(scanf("%lld%lld",&ch,&cv) && (ch||cv)) { for(i=0;i<9;i++) { scanf("%d",&a[i]); if(a[i] == 0) S.pos = i; } S.cantor = Cantor(a); S.cost = 0; for(i=0;i<9;i++) scanf("%d",&b[i]); E.cantor = Cantor(b); getcantor(S.cantor,a); getcantor(E.cantor,b); ans = (1LL<<62); bfs(); printf("%lld\n",ans); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。