欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java?九宮重排(滿分解法)

 更新時(shí)間:2022年05月24日 08:27:12   作者:愛敲代碼的三毛  
本文主要介紹了Java?九宮重排(滿分解法),文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下

題目

如下圖的九宮格中,放著 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)文章

最新評(píng)論