Java?九宮重排(滿分解法)
題目
如下圖的九宮格中,放著 1 ~ 8 的數(shù)字卡片,還有一個(gè)格子空著。與空格子相鄰的格子中的卡片可以移動(dòng)到空格中。 經(jīng)過若干次移動(dòng),可以形成圖 2 所示的局面。
我們把上圖的局面記為:12345678.
把下圖的局面記為:123.46758
顯然是按從上到下,從左到右的順序記錄數(shù)字,空格記為句點(diǎn)。
題目的任務(wù)是已知九宮的初態(tài)和終態(tài),求最少經(jīng)過多少步的移動(dòng)可以到達(dá)。如果無論多少步都無法到達(dá),則輸出 -1。
輸入描述
輸入第一行包含九宮的初態(tài),第二行包含九宮的終態(tài)。
輸出描述
輸出最少的步數(shù),如果不存在方案,則輸出 -1。
輸入
12345678.
123.46758
輸出
3
思路
求最少步數(shù),典型的廣搜
- 題目讓我們求最少步數(shù),我們可以模擬空格的移動(dòng)
- 通過字符串的下標(biāo)交換字符位置,模擬字符串的上下左右的移動(dòng),每次移動(dòng)通過set判斷該狀態(tài)是否已經(jīng)移動(dòng)過,如果沒有就入隊(duì)列
- 上(-3)下(+3)左(-1)右(+1)
- 判斷每次的下標(biāo)是否合法,越界只要判斷示是否在字符串長(zhǎng)度范圍內(nèi)
關(guān)鍵代碼:
(pos%3 != index%3 && pos/3 != index/3)
因?yàn)楫?dāng)前位置和上下都只是差3,左右都只是差1
如果是左右就一定滿足,下標(biāo)/3相等
如果是上下就一定滿足,下標(biāo)%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(); // 枚舉字符串下標(biāo)的上下左右 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; // 標(biāo)記是否已經(jīng)找到 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]; // 當(dāng)新的位置不是空格的上下左右或者已經(jīng)越界 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); } } }
到此這篇關(guān)于Java 九宮重排(滿分解法)的文章就介紹到這了,更多相關(guān)Java 九宮重排內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Java:DocumentBuilderFactory調(diào)用XML的方法實(shí)例
Java:DocumentBuilderFactory調(diào)用XML的方法實(shí)例,需要的朋友可以參考一下2013-04-04mybatis-plus自定義排序的實(shí)現(xiàn)
本文主要介紹了mybatis-plus自定義排序的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-01-01Springmvc如何實(shí)現(xiàn)向前臺(tái)傳遞數(shù)據(jù)
這篇文章主要介紹了Springmvc如何實(shí)現(xiàn)向前臺(tái)傳遞數(shù)據(jù),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-07-07SpringBoot屬性綁定與bean屬性校驗(yàn)實(shí)現(xiàn)方法詳解
這篇文章主要介紹了SpringBoot屬性綁定與bean屬性校驗(yàn)實(shí)現(xiàn)方法,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)吧2022-11-11Java實(shí)現(xiàn)兩人五子棋游戲(五) 判斷是否有一方勝出
這篇文章主要為大家詳細(xì)介紹了Java實(shí)現(xiàn)兩人五子棋游戲,判斷是否有一方勝出,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-03-03springboot日志文件名稱叫l(wèi)ogback-spring.xml的原因解析
這篇文章主要介紹了springboot日志文件名稱為什么叫l(wèi)ogback-spring.xml,本文給大家講解的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2023-08-08Springboot基于websocket實(shí)現(xiàn)簡(jiǎn)單在線聊天功能
這篇文章主要介紹了Springboot基于websocket實(shí)現(xiàn)簡(jiǎn)單在線聊天功能,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-06-06