题目描述

算法1

Java 代码

import java.io.*;
import java.util.*;

class Main{
    static void swap(char[] a, int i, int j) {
        char tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    private static int bfs(String start, String end){
        Map<String, Integer> map = new HashMap<>();
        Queue<String> q = new LinkedList<>();
        q.add(start);
        map.put(start, 0);
        int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        while(!q.isEmpty()){
            String s = q.poll();
            int dis = map.get(s);
            if (s.equals(end)) return dis;
            // 获得x的位置
            int k = s.indexOf('x');
            // x in graph postion
            int x = k / 3, y = k % 3;
            for (int[] dir:dirs) {
                int a = x + dir[0];
                int b = y + dir[1];
                if (a < 3 && a >= 0 && b < 3 && b >= 0) {
                    // 对字符串中的字符进行更改
                    char[] arr = s.toCharArray();
                    swap(arr, k, a * 3 + b);
                    String str = new String(arr);
                    // 如果没有被遍历过
                    if (map.get(str) == null) {
                        map.put(str, map.get(s) + 1);
                        q.offer(str);
                    } 
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split("\\s+");
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length; i++) {
            sb.append(s[i]);
        }
        String end = "12345678x";
        System.out.println(bfs(sb.toString(), end));
    }

}