Java 九宮重排(滿分解法)
題目
如下圖的九宮格中,放著 1 ~ 8 的數字卡片,還有一個格子空著。與空格子相鄰的格子中的卡片可以移動到空格中。 經過若幹次移動,可以形成圖 2 所示的局面。
我們把上圖的局面記為:12345678.
把下圖的局面記為:123.46758
顯然是按從上到下,從左到右的順序記錄數字,空格記為句點。
題目的任務是已知九宮的初態和終態,求最少經過多少步的移動可以到達。如果無論多少步都無法到達,則輸出 -1。
輸入描述
輸入第一行包含九宮的初態,第二行包含九宮的終態。
輸出描述
輸出最少的步數,如果不存在方案,則輸出 -1。
輸入
12345678.
123.46758
輸出
3
思路
求最少步數,典型的廣搜
- 題目讓我們求最少步數,我們可以模擬空格的移動
- 通過字符串的下標交換字符位置,模擬字符串的上下左右的移動,每次移動通過set判斷該狀態是否已經移動過,如果沒有就入隊列
- 上(-3)下(+3)左(-1)右(+1)
- 判斷每次的下標是否合法,越界隻要判斷示是否在字符串長度范圍內
關鍵代碼:
(pos%3 != index%3 && pos/3 != index/3)
因為當前位置和上下都隻是差3,左右都隻是差1
如果是左右就一定滿足,下標/3相等
如果是上下就一定滿足,下標%3相等
代碼
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String start = sc.next(); String end = sc.next(); // 枚舉字符串下標的上下左右 int[] upDownLeftRight = {-3,3,-1,1}; // 去重 Set<String> set = new HashSet<>(); Queue<String> queue = new LinkedList<>(); set.add(start); queue.offer(start); int count = 0; // 標記是否已經找到 boolean flag = false; while (!queue.isEmpty()) { int size = queue.size(); while (size-- != 0) { String s = queue.peek(); // 空格位置 int index = s.indexOf("."); for (int i = 0; i < 4; i++) { int pos = index + upDownLeftRight[i]; // 當新的位置不是空格的上下左右或者已經越界 if (pos < 0 || pos > 8 || (pos%3 != index%3 && pos/3 != index/3)) { continue; } char c = s.charAt(pos); char[] ch = s.toCharArray(); ch[pos] = ch[index]; ch[index] = c; String str = new String(ch); if (str.equals(end)) { flag = true; break; } if (set.add(str)) { queue.offer(str); } } queue.poll(); } count++; if (flag) { break; } } if (flag) { System.out.println(count); } else { System.out.println(-1); } } }
到此這篇關於Java 九宮重排(滿分解法)的文章就介紹到這瞭,更多相關Java 九宮重排內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- Java中隊列Queue和Deque的區別與代碼實例
- Java控制臺版五子棋的簡單實現方法
- Java基礎題新手練習(三)
- Java Stack與Queue詳解
- java編程學習輸入輸出詳解看完快速上手