AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 校园
  • 应用
  • 文章
    • 题解
    • 分享
    • 问答
  • 吐槽
  • 登录/注册

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

作者: 作者的头像   昆卡 ,  2022-01-15 01:05:45 ,  所有人可见 ,  阅读 42


1


java中没有swap函数,也不能对字符串进行直接操作,所以改变x的位置的操作需要先转化为char数组,然后再手写swap函数,再用String的valueOf()方法将char数组转化为字符串保存

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

public class Main{
    //本题难点需要进行状态更新,每次变换x的位置时,需要把当前状态记录下来,防止下次再次遍历出现死循环
    //如果使用二维数组来保存数据,很难实现状态更新
    static int[][] dir = {{-1,0},{0,1},{1,0},{0,-1}};
    static Queue<String> qu = new LinkedList<String>();
    static Map<String, Integer> map = new HashMap<String, Integer>();
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String st = br.readLine().replace(" ", "");
        int stx=0,sty=0;
        System.out.print(bfs(st));
    }
    public static int bfs(String st){
        map.put(st, 0);
        qu.add(st);
        while(!qu.isEmpty()){
            st = qu.poll();
            if(st.equals("12345678x")) return map.get(st);
            int dis = map.get(st);
            int x = st.indexOf('x')/3;//将字符串转化为想象中的一个二维数组,记录x的横坐标
            int y = st.indexOf('x')%3;//将字符串转化为想象中的一个二维数组,记录x的纵坐标
            int xdis = st.indexOf('x');
            char[] sc = st.toCharArray();
            for(int i=0;i<4;i++){
                int newx = x+dir[i][0],newy = y+dir[i][1];
                if(newy<3&&newx>=0&&newx<3&&newy>=0){
                    char temp = sc[xdis];
                    sc[xdis]= sc[newx*3+newy];
                    sc[newx*3+newy] = temp;
                    if(!map.containsKey(String.valueOf(sc))) {//如果当前搜索的状态已经出现过那么久直接跳过,否则加入队列
                        map.put(String.valueOf(sc), dis+1);
                        qu.add(String.valueOf(sc));
                    }
                    temp = sc[xdis];
                    sc[xdis]= sc[newx*3+newy];
                    sc[newx*3+newy] = temp;
                }
            }
        }
        return -1;
    }
}

0 评论

你确定删除吗?
1024
x

© 2018-2022 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息