題目
在一個 2 x 3 的板上（board）有 5 塊磚瓦，用數字 1~5 來表示, 以及一塊空缺用?0?來表示.
一次移動定義為選擇?0?與一個相鄰的數字（上下左右）進行交換.
最終當板?board?的結果是?[[1,2,3],[4,5,0]]?謎板被解開。
給出一個謎板的初始狀態，返回最少可以通過多少次移動解開謎板，如果不能解開謎板，則返回 -1 。
- 示例：
輸入：board = [[1,2,3],[4,0,5]]
輸出：1
解釋：交換 0 和 5 ，1 步完成
輸入：board = [[1,2,3],[5,4,0]]
輸出：-1
解釋：沒有辦法完成謎板
輸入：board = [[4,1,2],[5,0,3]]
輸出：5
解釋：
最少完成謎板的最少移動次數是 5 ，
一種移動路徑:
尚未移動: [[4,1,2],[5,0,3]]
移動 1 次: [[4,1,2],[0,5,3]]
移動 2 次: [[0,1,2],[4,5,3]]
移動 3 次: [[1,0,2],[4,5,3]]
移動 4 次: [[1,2,0],[4,5,3]]
移動 5 次: [[1,2,3],[4,5,0]]
輸入：board = [[3,2,4],[1,5,0]]
輸出：14
提示：
- board?是一個如上所述的 2 x 3 的數組.
- board[i][j]?是一個?[0, 1, 2, 3, 4, 5]?的排列.
解題思路
- 使用字符串代表謎板的狀態
board = [[1,2,3],[4,0,5]]1 2 3
4 0 5使用字符串 123405表示
所以每一個字符串就代表謎板的一個狀態
- 廣度優先搜索
利用隊列實現廣度優先搜索，根據0所在位置，將0和周圍的數字進行交換，從而衍生出若干種情況加入隊列
代碼
class Solution {public void swagg(char[] tar,int x,int y) {char temp=tar[x];tar[x]=tar[y];tar[y]=temp;}public int slidingPuzzle(int[][] board) {StringBuilder stringBuilder=new StringBuilder();for (int i=0;i<board.length;i++)for (int j=0;j<board[0].length;j++){stringBuilder.append(board[i][j]);}Set<String> set=new HashSet<>();Queue<String> queue=new LinkedList<>();queue.add(stringBuilder.toString());int res=0;String s=null;while (!queue.isEmpty()){int cur=queue.size();for (int i=0;i<cur;i++){s = queue.poll();if(s.equals("123450")) return res;char[] th=s.toCharArray();for (int j=0;j<6;j++){if(th[j]=='0'){int x=j%3,y=j/3;if(y==1){swagg(th,j,x);String temp=new String(th);if(!set.contains(temp))queue.add(temp);set.add(temp);swagg(th,j,x);}else {swagg(th,j,x+3);String temp=new String(th);if(!set.contains(temp))queue.add(temp);set.add(temp);swagg(th,j,x+3);}if(x>0){swagg(th,j,j-1);String temp=new String(th);if(!set.contains(temp))queue.add(temp);set.add(temp);swagg(th,j,j-1);}if(x<2){swagg(th,j,j+1);String temp=new String(th);if(!set.contains(temp))queue.add(temp);set.add(temp);swagg(th,j,j+1);}}}}res++;}return -1;}
}
