簡(jiǎn)直難到?jīng)]朋友。

雙向bfs + 剪枝。

剪枝策略：

對(duì)于2--5位置上的數(shù)，僅僅有當(dāng)光標(biāo)在相應(yīng)位置時(shí)通過swap ，up。down來改變。那么當(dāng)當(dāng)前位置沒有達(dá)到目標(biāo)狀態(tài)時(shí)，left和right無意義。

好了。僅僅剪掉這里就過掉了。。。

還有比較炫酷的方法實(shí)現(xiàn)枚舉720種排列。

。。

然后狀壓什么的。。。

功力不夠全然看不懂。

。。。

#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <cmath> #include <stack> #include <map>#pragma comment(linker, "/STACK:1024000000"); #define EPS (1e-8) #define LL long long #define ULL unsigned long long #define _LL __int64 #define _INF 0x3f3f3f3f #define Mod 9999991using namespace std;short int mark[1000000][7][2];struct Q {int ans,sta,site,fl; };int s[10];int pre[] = {1000000,100000,10000,1000,100,10,1};// 0 1 2 3 4 5 6 inline int Cal(int num,int site,int ch) {int temp = (num/pre[site])%10 + ch;if(0 <= temp && temp <= 9)return num/pre[site-1]*pre[site-1] + temp*pre[site] + num%pre[site];return num; }inline int Swap(int num,int site,int m) {int t1 = (num/pre[site])%10;int t2 = (num/pre[m])%10;if(t1 == t2)return num;num = num/pre[site-1]*pre[site-1] + t2*pre[site] + num%pre[site];num = num/pre[m-1]*pre[m-1] + t1*pre[m] + num%pre[m];return num; }bool Judge(int site,int a,int b) {if((a/pre[site])%10 == (b/pre[site])%10)return true;return false; }int bfs(int a,int b) {memset(mark,-1,sizeof(mark));queue<Q> q;Q s,t;s.sta = a;s.fl = 0;s.ans = 0;s.site = 1;mark[s.sta][s.site][s.fl] = 0;q.push(s);s.sta = b;s.ans = 0;s.fl = 1;for(int i = 1;i <= 6; ++i){s.site = i;mark[s.sta][s.site][s.fl] = 0;q.push(s);}while(q.empty() == false){t = q.front();q.pop();// printf("site = %2d sta = %6d fl = %2d ans = %2d\n",t.site,t.sta,t.fl,t.ans);if(mark[t.sta][t.site][t.fl^1] != -1){return mark[t.sta][t.site][t.fl^1] + t.ans;}s.fl = t.fl;s.ans = t.ans+1;//lefts.sta = t.sta;if(t.site > 1 && (t.site < 2 || t.site > 5 || Judge(t.site,t.sta,t.fl == 0 ?

b : a))) { s.site = t.site-1; if(mark[s.sta][s.site][s.fl] == -1) { mark[s.sta][s.site][s.fl] = s.ans; q.push(s); } } //right if(t.site < 6 && (t.site < 2 || t.site > 5 || Judge(t.site,t.sta,t.fl == 0 ? b : a))) { s.site = t.site+1; if(mark[s.sta][s.site][s.fl] == -1) { mark[s.sta][s.site][s.fl] = s.ans; q.push(s); } } //up s.sta = Cal(t.sta,t.site,1); s.site = t.site; if(mark[s.sta][s.site][s.fl] == -1) { mark[s.sta][s.site][s.fl] = s.ans; q.push(s); } //down s.sta = Cal(t.sta,t.site,-1); if(mark[s.sta][s.site][s.fl] == -1) { mark[s.sta][s.site][s.fl] = s.ans; q.push(s); } //swap0 if(t.site != 1) { s.sta = Swap(t.sta,t.site,1); if(mark[s.sta][s.site][s.fl] == -1) { mark[s.sta][s.site][s.fl] = s.ans; q.push(s); } } //swap1 if(t.site != 6) { s.sta = Swap(t.sta,t.site,6); if(mark[s.sta][s.site][s.fl] == -1) { mark[s.sta][s.site][s.fl] = s.ans; q.push(s); } } } return 0; } int main() { //freopen("data.txt","r",stdin); int a,b; scanf("%d %d",&a,&b); printf("%d\n",bfs(a,b)); return 0; }

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的POJ 1184 聪明的打字员的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。