題目&解題思路：

代碼：

import java.io.PushbackInputStream; import java.util.*;public class Puzzle_9 {public static final int N = 3;public static final int N2 = 9;public static final int dx[] = {-1, 0, 1, 0};public static final int dy[] = {0, -1, 0, 1};public static final char dir[] = {'u', 'l', 'd', 'r'};public static class Puzzle implements Comparable {int f[] = new int[N2];int space;String path;@Overridepublic int compareTo(Object obj){Puzzle p = (Puzzle)obj;int cnt = 0;for (int i=0;i<N2;i++){if(p.f[i]==this.f[i])cnt++;else{return -1;}}if (cnt==9){return 0;}else{return -1;}}}//如果第i個元素對應的不是(i+1)，那么就返回falsepublic static boolean isTarget(Puzzle p){for (int i=0;i<N2;i++){if(p.f[i]!=(i+1)){return false;}}return true;}public static String bfs(Puzzle s){ArrayDeque<Puzzle> Q = new ArrayDeque<>();HashSet<Puzzle> V = new HashSet<>();Puzzle u = new Puzzle();Puzzle v = new Puzzle();s.path = "";//將傳入的路徑設置為空Q.addLast(s);//入隊V.add(s);//將s的狀態添加進入歷史訪問集合while (!Q.isEmpty()){u = copyPuzzle(Q.peek());Q.removeFirst();if(isTarget(u))return u.path;//如果完成目標了，則返回u的路徑int sx = u.space/N;//用于對當前空格的定位int sy = u.space%N;for (int r=0;r<4;r++){int tx = sx + dx[r];//設置4個方位的移動int ty = sy + dy[r];if(tx<0||ty<0||tx>=N||ty>=N)continue;v = copyPuzzle(u);//移動空格int temp = v.f[u.space];v.f[u.space] = v.f[tx*N+ty];v.f[tx*N+ty] = temp;//設置空格位置v.space = tx*N+ty;//判斷這個狀態歷史上是否發生，如果發生就跳過，沒發生就執行：if(!isContain(V,v)){V.add(v);//將當前狀態加入歷史記錄集合v.path += dir[r];//將移動操作添加到其路徑中Q.addLast(v);//將當前狀態入隊等待操作}}}return "unsolvable";}public static boolean isContain(HashSet<Puzzle> V, Puzzle v){Iterator<Puzzle> it = V.iterator();while(it.hasNext()){Puzzle element = it.next();if(element.compareTo(v)==0){return true;};}return false;}public static Puzzle copyPuzzle(Puzzle p){Puzzle p1 = new Puzzle();p1.space = p.space;p1.path = p.path;for (int i=0;i<N2;i++){p1.f[i] = p.f[i];}return p1;}public static void main(String[] args) {Scanner cin = new Scanner(System.in);Puzzle in = new Puzzle();for (int i=0;i<N2;i++){in.f[i] = cin.nextInt();if(in.f[i] == 0){in.f[i] = N2;in.space = i;}}String ans = bfs(in);System.out.println(ans.length());} }

輸入：

1 3 0 4 2 5 7 8 6

輸出：

4

這次的代碼有很多值得玩味的地方，雖然耽誤了很多時間，踩了很多坑，也總結很多經驗。

1.目的：想要用對象2存入對象1中的所有值。
錯誤做法：將對象2賦值給對象1。
結果：更改對象2時，對象1也會同時更改。
原因：將對象2賦值給對象1的動作實際上是把對象2的地址賦給對象1，因此無論操作對象1還是對象2都是操作的同一片內存空間。
解決方案：為對象1開辟一份新的內存空間，將對象2中所有的值賦給對象1，甚至是對象1中的數組也要以元素為單位一一賦值。
示例代碼：

public static Puzzle copyPuzzle(Puzzle p){Puzzle p1 = new Puzzle();p1.space = p.space;p1.path = p.path;for (int i=0;i<N2;i++){p1.f[i] = p.f[i];}return p1;}

2.目的：如何自定義比較兩個對象是否一致。
錯誤做法：再寫一個函數比較，很麻煩。
解決方案：實現Comparable接口，并重寫compareTo方法，這樣就可以定義一個比較器，從而比較別的對象是不是和自己相同。
示例代碼：

public static class Puzzle implements Comparable {int f[] = new int[N2];int space;String path;@Overridepublic int compareTo(Object obj){Puzzle p = (Puzzle)obj;int cnt = 0;for (int i=0;i<N2;i++){if(p.f[i]==this.f[i])cnt++;else{return -1;}}if (cnt==9){return 0;}else{return -1;}}}

3.對于一個ArrayDeque隊列，添加刪除元素時，最好用addLast，removeFirst這樣的函數，否則使用push、add、remove、pop就不確定從哪頭插入元素刪除元素了，這就失去了隊列的意義，也是今天卡了很久的原因

總結

以上是生活随笔為你收集整理的挑战程序设计竞赛（算法和数据结构）——19.2九宫格拼图问题的JAVA实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。