AcWing 845. 八数码 java

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 845. 八数码 java 原题链接中等

作者：

拿不到offer不改名 , 2020-04-13 17:54:22 , 所有人可见 , 阅读 1576

6

4

最小步数模型

这题的算法思想就是将每一串字符都想象成一个点，已知起点和终点,每一次更新相邻的节点，采用bfs得到到达终点的最短路径，然后这里使用map来存储对应字符串和对应的遍历顺序

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;
    }
    static int bfs(String start, String end) {
        Map<String, Integer> map = new HashMap<>();
        Queue<String> q = new LinkedList<>();
        q.offer(start);
        map.put(start, 0);

        int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
        while (!q.isEmpty()) {
            String s = q.poll();
            if (s.equals(end)) return map.get(s);

            // 获得x的位置
            int k = s.indexOf('x');
            int x = k / 3, y = k % 3;
            for (int i = 0; i < 4; i++) {
                int a = x + dx[i], b = y + dy[i];
                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(" ");
        String start = "";
        for (int i = 0; i < s.length; i++) start += s[i];
        String end = "12345678x";
        System.out.println(bfs(start, end));
    }
}

5 评论

学不会我就死 2022-01-26 18:38

String start = "";
        for (int i = 0; i < s.length; i++) start += s[i];
        String end = "12345678x";

为啥不能写成

String start =s.toString();

为啥这么写会爆数组越界啊

lian773596423 2020-12-17 22:07

这位大哥能否帮我看看哪里出错了呜呜呜，感激涕零
、、、

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;

/*
* @author 文思涌
* 845.八数码
* 2020年12月17日
/
public class Main {
private static String start=”“;
private static String end=”12345678x”;
public static int bfs() {
Queue[HTML_REMOVED] queue=new LinkedList[HTML_REMOVED]();
Map[HTML_REMOVED] dist=new HashMap<>();//记录实现到满足这字符串的最短距离
dist.put(start, 0);//初始化为0
queue.offer(start);

    //只初始化一次就行
    int[] dx= {1,-1,0,0},dy= {0,0,1,-1};//比较常见的一步，用来记录找寻变化的坐标
    while(!queue.isEmpty()) {
        String str=queue.poll();
        if(end.equals(str))//如果出队中已经符合，则返回哈希表的值
            return dist.get(str);

        int index=start.indexOf('x');
        int x=index/3,y=index%3;//很重要的一步，让一维变成二维的；

        for(int i=0;i<4;i++) {
            int a=x+dx[i],b=y+dy[i];
            if(a>=0&&a<3&&b>=0&&b<3) {
                int after=a*3+b;//让变化后的二维下标变到一维下标去
                String t=swap(str.toCharArray(), index, after);//交换x与它要交换的值
                if(!dist.containsKey(t)) {//第一次存的距离就是最短距离，所以以后不用再存了。若还没到变化到这里，则将所需要的操作次数存到里面
                    dist.put(t, dist.get(str)+1);
                    //System.out.println(dist.put(t, dist.get(str)+1));
                    queue.offer(t);
                }
            }
        }
    }
    return -1;
}
public static String swap(char[] c,int a,int b) {
    char temp=c[a];
    c[a]=c[b];
    c[b]=temp;
    /*String aString=c.toString();//很重要的一点就是不能返回String，而是一个地址

*/
return new String(c);//用这种就可以转变成String数组
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
for(int i=0;i<9;i++) {
String str=scanner.next();
start+=str;
}
//System.out.println(start.indexOf(‘x’));
System.out.println(bfs());
}
}

、、、

拿不到offer不改名 2021-01-25 09:47

出现的主要问题的地方是

int index=start.indexOf('x');
int x=index/3,y=index%3;//很重要的一步，让一维变成二维的；

应该修改为

 int index = str.indexOf('x');
 int x = index / 3, y = index % 3;//很重要的一步，让一维变成二维的；

拿不到offer不改名 2021-01-25 09:47 回复了拿不到offer不改名的评论

另外注意中英文的引号

lian773596423 2021-01-25 14:08 回复了拿不到offer不改名的评论

原来如此，谢谢大佬

App 内打开