題目Eight
Problem Description
這個(gè)15難題已經(jīng)存在了100多年了，即使你不知道它的名字，你也看到了。它由15個(gè)滑動(dòng)瓦片構(gòu)成，每個(gè)滑動(dòng)瓦片的數(shù)量從1到15，并且全部裝入4乘4幀，缺少一個(gè)瓦片。我們稱(chēng)之為缺失的瓦片’x’;難題的目的是安排瓷磚，以便它們按以下順序排列：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 x
其中唯一合法的操作是與其共享邊緣的一個(gè)瓷磚交換’x’。作為一個(gè)例子，下面的一系列動(dòng)作解決了一個(gè)稍微混亂的難題：
1 2 3 4 -> 1 2 3 4 -> 1 2 3 4 -> 1 2 3 4
5 6 7 8 -> 5 6 7 8 -> 5 6 7 8 -> 5 6 7 8
9 x 10 12 -> 9 10 x 12 -> 9 10 11 12 -> 9 10 11 12
13 14 11 15 -> 13 14 11 15 -> 13 14 x 15 -> 13 14 15 x
r-> d-> r->

上一行中的字母表示每個(gè)步驟中’x’瓦片的哪個(gè)鄰居與’x’瓦片交換;法律價(jià)值分別為’r’，‘l’，‘u’和’d’，分別為正，左，上和下。
并非所有的謎題都可以解決;在1870年，一個(gè)名叫薩姆·洛伊德的人因發(fā)布了一個(gè)難以解決的難題而聞名
挫敗了很多人。事實(shí)上，只需要交換兩塊拼塊（當(dāng)然，不包括缺失的“x”拼塊），您所需要做的就是拼成一個(gè)難以解決的難題。
在這個(gè)問(wèn)題中，你將編寫(xiě)一個(gè)程序來(lái)解決不太知名的8拼圖，它是由3×3的拼圖組成的安排。
輸入
您將收到有關(guān)8拼圖配置的幾個(gè)說(shuō)明。一個(gè)描述只是一個(gè)在其初始位置的圖塊列表，其中行從上到下列出，并且在一行內(nèi)從左到右列出圖塊，其中圖塊由數(shù)字1到8表示，再加上’x’ 。例如，這個(gè)難題

1 2 3
x 4 6
7 5 8

is described by this list:

1 2 3 x 4 6 7 5 8
Output
如果拼圖沒(méi)有解決方案，或者將完全由字母’r’，‘l’，'u’和’d’組成的字符串描述為一系列移動(dòng)產(chǎn)生一個(gè)解決方案。該字符串不應(yīng)包含空格，并從行首開(kāi)始。不要在案件之間打印空行。
Sample Input
2 3 4 1 5 x 7 6 8

Sample Output
ullddrurdllurdruldr
問(wèn)題分析：因?yàn)橛卸嘟M測(cè)試數(shù)據(jù)，我使用的是bfs 康托，bfs跑一遍，遍歷所有情況，然后輸出輸入的值，我把初始數(shù)組變?yōu)?23456789，因?yàn)檩斎氲膞和9在字符串大小是等效的。值得注意的是路徑要倒著寫(xiě)，因?yàn)槲覀冏叩倪^(guò)程是取反過(guò)程。還有注意的是一維二維數(shù)組的轉(zhuǎn)換，計(jì)算康托值用一維數(shù)組，但是移動(dòng)要變成二維注意Java的對(duì)象克隆，不然你的數(shù)組會(huì)被更改。
還有大佬用A*和雙向bfs的可以了解下。方法也很巧妙。
貼上代碼

import java.util.ArrayDeque; import java.util.Queue; import java.util.Scanner; public class 杭電1043 {static int jiecheng[]= {1,1,2,6,24,120,720,5040,40320};public static void main(String[] args) {Scanner sc=new Scanner(System.in); char start[][]= {{'1','2','3'},{'4','5','6'},{'7','8','9'}}; //初始狀態(tài)int judgel[]=new int[362880];//標(biāo)記String path []=new String [362880];//記錄路徑Queue q1=new ArrayDeque();judgel[0]=1;path[0]="";//初始化（0到0要特殊處理）q1.add(start);//入隊(duì)while(!q1.isEmpty()){char[][]exa=q1.poll();int kang=kangtuo(exa);//對(duì)應(yīng)的位置; int x1=0,y1=0;for(int i=0;i<3;i )//找打'x'（9）的位置{for(int j=0;j<3;j ){if(exa[i][j]=='9'){x1=i;y1=j;} }}int k2=0; //執(zhí)行bfs{char[][]t2=r(exa,x1,y1); k2=kangtuo(t2);if(judgel[k2]==0) {q1.add(t2);path[k2]='l' path[kang];judgel[k2]=1;}} {char[][]t1=l(exa,x1,y1); k2=kangtuo(t1);if(judgel[k2]==0) {q1.add(t1);path[k2]='r' path[kang];judgel[k2]=1;}} {char[][]t4=down(exa,x1,y1); k2=kangtuo(t4);if(judgel[k2]==0) {q1.add(t4);path[k2]='u' path[kang];judgel[k2]=1;}}{char[][]t3=up(exa,x1,y1); k2=kangtuo(t3);if(judgel[k2]==0) {q1.add(t3);path[k2]='d' path[kang];judgel[k2]=1;}} }while(sc.hasNextLine()){String a=sc.nextLine();String a2[]=a.split(" "); char c[][]=new char[3][3];for(int i=0;i<9;i ){ c[i/3][i%3]=a2[i].charAt(0); }String value=path[kangtuo(c)];//直接輸出保存過(guò)的值if(value==null) {System.out.println("unsolvable"); }else if(value=="") {System.out.println("lr");}else System.out.println(value); }}static int kangtuo(char[][] start) {int m=0;int n=0;char b[]=new char[9];for(int i=0;i<3;i ){for(int j=0;j<3;j )b[i*3 j]=start[i][j];}for(int i=0;i<9;i ){m=0;for(int j=i 1;j<9;j ){if(b[i]>b[j])m ;}n =m*jiecheng[8-i];}return n; }static char[][] l (char a[][],int x1,int y1){char b[][]=new char[3][3];b[0]=a[0].clone();b[1]=a[1].clone();b[2]=a[2].clone();if(y1>0) {char team=b[x1][y1];b[x1][y1]=b[x1][y1-1];b[x1][y1-1]=team;}return b; }static char[][] r (char a[][],int x1,int y1){char b[][]=new char[3][3];b[0]=a[0].clone();b[1]=a[1].clone();b[2]=a[2].clone();if(y1<2) {char team=b[x1][y1];b[x1][y1]=b[x1][y1 1];b[x1][y1 1]=team;}return b; }static char[][] up (char a[][],int x1,int y1){char b[][]=new char[3][3];b[0]=a[0].clone();b[1]=a[1].clone();b[2]=a[2].clone();if(x1==1||x1==2) {char team=b[x1][y1];b[x1][y1]=b[x1-1][y1];b[x1-1][y1]=team;}return b; }static char[][] down (char a[][],int x1,int y1){char b[][]=new char[3][3];b[0]=a[0].clone();b[1]=a[1].clone();b[2]=a[2].clone();if(x1==0||x1==1) {char team=b[x1][y1];b[x1][y1]=b[x1 1][y1];b[x1 1][y1]=team;}return b; }} 《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專(zhuān)家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的杭电1043java实现bfs一遍的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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