魔板:
Problem Description
在魔方風靡全球之后不久，Rubik先生發(fā)明了它的簡化版——魔板。魔板由8個同樣大小的方塊組成，每個方塊顏色均不相同，可用數(shù)字1-8分別表示。任一時刻魔板的狀態(tài)可用方塊的顏色序列表示：從魔板的左上角開始，按順時針方向依次寫下各方塊的顏色代號，所得到的數(shù)字序列即可表示此時魔板的狀態(tài)。例如，序列(1,2,3,4,5,6,7,8)表示魔板狀態(tài)為：
1 2 3 4
8 7 6 5
對于魔板，可施加三種不同的操作，具體操作方法如下：
A: 上下兩行互換,如上圖可變換為狀態(tài)87654321
B: 每行同時循環(huán)右移一格,如上圖可變換為41236785
C: 中間4個方塊順時針旋轉(zhuǎn)一格,如上圖可變換為17245368

給你魔板的初始狀態(tài)與目標狀態(tài)，請給出由初態(tài)到目態(tài)變換數(shù)最少的變換步驟，若有多種變換方案則取字典序最小的那種。

Input
每組測試數(shù)據(jù)包括兩行，分別代表魔板的初態(tài)與目態(tài)。

Output
對每組測試數(shù)據(jù)輸出滿足題意的變換步驟。

Sample Input
12345678
17245368
12345678
82754631

Sample Output
C
AC
分析核心：映射，bfs，康托（康托只是一個工具）
1：剛開始的做法：把沒輸入的兩行當作字符串，寫出函數(shù)ABC的操作過程，然后每輸入一個數(shù)就把他當作初態(tài)然后運行bfs。輸出結果。當然，肯定是要標記進行bfs的。我就建立了boolean【88888888】數(shù)組對其標記，結果：wa
2：后來參考了別人的做法：首先把字符串的處理變成char【】數(shù)組的處理。我發(fā)現(xiàn)別人都用康托展開。后來想了一下，這八個數(shù)的排列是有順序并且沒有重復的，總共就8！種情況，我用了88888888數(shù)組明顯造成資源浪費。然后就學習了下康托展開。對于康托，只是一種表示的工具，可以看作是一種巧妙的數(shù)據(jù)結構，但是不是算法。附上康托展開實現(xiàn)

static int kangtuo(char a[])//轉(zhuǎn)化為康托展開的值{int jiecheng[]= {1,1,2,6,24,120,720,5040};int m=0,n=0;for(int i=0;i<8;i ){m=0;for(int j=i 1;j<8;j ){if(a[i]>a[j])m ;}n =m*jiecheng[7-i];}return n; }

這樣就可以用40321個數(shù)表示所有能出現(xiàn)的情況，而不需要88888888個。但是結果還是wa

3：請教學長之后，想到了用映射。就是跑一遍bfs，而不是跑多遍bfs，一遍bfs記錄所有的結果，你或許會問初態(tài)不一樣，終態(tài)不一樣怎么辦，你要轉(zhuǎn)化，把所有的初態(tài)轉(zhuǎn)化成12245678，所有終態(tài)轉(zhuǎn)化為對應數(shù)字，直接輸入對應的記錄過的結果，簡而言之就是我后面輸入輸出，我只在意他位置的變化，而不是數(shù)字的變化，舉個簡單例子，如果輸入的是321，213，你可以看到第一個數(shù)3跑到第三位上，2跑到第一位上，1跑到第二位上，（這里就是把三看成1，把2看成2，把1看成3）他的執(zhí)行步驟其實和123跑到231，看看兩組數(shù)組的位置是否對應一樣。理解這個就可以了。
附上代碼如下：

import java.util.ArrayDeque; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class 杭電1430 {static int jiecheng[]= {1,1,2,6,24,120,720,5040};public static void main(String[] args) { Scanner sc=new Scanner(System.in); int jud[]=new int[40321];String path[]=new String[40321]; char start[]= {'1','2','3','4','5','6','7','8'};path[kangtuo(start)]="";//初始第一個數(shù)組元素是""而不是null Queueq1=new ArrayDeque();q1.add(start); while(!q1.isEmpty()){char t2[]=q1.poll(); //去頭并返回int exam=kangtuo(t2);//當前的康托展開值jud[exam]=1;{ char p1[]=a(t2);int kang=kangtuo(p1);//分別走三部并且判斷是否可走 if(jud[kang]==0) {q1.add(p1);path[kang]=path[exam] 'A';jud[kang]=1; }char p2[]=b(t2); kang=kangtuo(p2); if(jud[kang]==0) {q1.add(p2);path[kang]=path[exam] 'B'; jud[kang]=1;}char p3[]=c(t2); kang=kangtuo(p3); if(jud[kang]==0) {q1.add(p3);path[kang]=path[exam] 'C';jud[kang]=1; } } } while(sc.hasNextLine()){ String c=sc.nextLine();//初始狀態(tài) String d=sc.nextLine();//結束狀態(tài) char c1[]=c.toCharArray();char d1[]=d.toCharArray();//轉(zhuǎn)化為字符數(shù)組d1= zhuanhua(c1,d1);System.out.println(path[kangtuo(d1)]); }}private static char[] zhuanhua(char[] c1, char[] d1) { for(int i=0;i<8;i ){for(int j=0;j<8;j ){if(d1[i]==c1[j]) {d1[i]=(char) (j 1 '0');break;}}}return d1; }static int kangtuo(char a[])//轉(zhuǎn)化為康托展開的值{int m=0,n=0;for(int i=0;i<8;i ){m=0;for(int j=i 1;j<8;j ){if(a[i]>a[j])m ;}n =m*jiecheng[7-i];}return n; }static void swap(char a[],int b,int c){ char tem=a[b];a[b]=a[c];a[c]=tem; } private static char[] a(char b[])//a的實現(xiàn)方法{char a[]=b.clone();//賦值b數(shù)組不改變b數(shù)組swap(a,0,7);swap(a,1,6);swap(a,2,5);swap(a,3,4);return a;}static char[] b(char b[]){char a[]=b.clone();swap(a,3,2);swap(a,2,1);swap(a,1,0);swap(a,4,5);swap(a,5,6);swap(a,6,7);return a;}static char[] c(char b[]){char a[]=b.clone();swap(a,1,6);swap(a,2,6);swap(a,5,6); return a;} }

康托只是一種工具，其中映射的道理，減少bfs的次數(shù)。才是最重要的。

總結

以上是生活随笔為你收集整理的杭电1430康托 bfs（java）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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