大喵喵不可爱

用户名：dmmbka

访问量：242

签　名：

等　　级
排　　名	40682
经　　验	371
参赛次数	0
文章发表	1
年　　龄	0
在职情况	学生
学　　校	南京工程学院
专　　业

　　自我简介：

TA的其他文章

Java版本双向BFS
浏览：146

你可能喜欢

Java版本双向BFS

　　作者: 大喵喵不可爱　　　　发表时间：2022-03-20 18:59:47 浏览：146　|　评论：0　

原题链接：蓝桥杯历届试题-九宫重排

# 算法选择
双向广度优先搜素

# 思路
按照题意，方阵的起点和终点都已经确定了，可以选择双向BFS复杂度
所谓双向BFS，即从起点往终点状态搜索的同时，从终点状态往起点状态搜索，同时分别维护一个Map，来记录到达某一状态的最小步数，算法的目的就是寻找某一中间状态state，起点和终点都能搜索到该状态

# Java代码

~~~java
import java.util.*;
class Main {
    static String s,t;
	//s是起点状态，t是终点状态
    static int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        s=scanner.nextLine();
        t=scanner.nextLine();
        int ans = bfs();
        if (ans==-1)
            System.out.println(-1);
        else
            System.out.println(ans);
    }

public static int bfs(){
        Deque<String> d1 = new ArrayDeque<>();
		//从起点往终点状态搜索
        Deque<String> d2 = new ArrayDeque<>();
		//反向搜索
        Map<String,Integer> m1 = new HashMap<>();
		//正向搜索的结果集
        Map<String,Integer> m2 = new HashMap<>();
		//反向搜索的结果集
        d1.addLast(s);
        d2.addLast(t);
        m1.put(s,0);
        m2.put(t,0);
        while (!d1.isEmpty()&&!d2.isEmpty()){
            int t = -1 ;
			//优先扩展比较小的队列，以维持两队列大小的平衡
            if (d1.size()<=d2.size()){
                t = update(d1,m1,m2);
            }else {
                t = update(d2,m2,m1);
            }
            if (t != -1)
                return t;
        }
        return -1;
    }

//需要处理的队列，cur是deque所对应的结果集，other是从另一个方向搜索对应的结果集
    public static int update(Deque<String> deque,Map<String,Integer> cur,Map<String,Integer> other){
        int size = deque.size();
        int index = -1;
        int x,y;
        while (size-->0){
            String poll = deque.pollFirst();
            index = getIndex(poll);
            x=index/3;y=index%3;
            for (int i=0;i<4;i++){
                int nx = x+dirs[i][0],ny = y+dirs[i][1];
                //下一个要移动到index位置的方块
                if (nx<0||nx>2||ny<0||ny>2)
                    continue;
                //无效数据
                int next = nx*3+ny;
                String state = swap(poll,next,index);
				//已经搜索过该状态
                if (cur.containsKey(state)) {
                    if (cur.get(state)>cur.get(poll)+1)
                        cur.put(state,cur.get(poll)+1);
                    else
                        continue;
					//千万不要直接continue，我在这卡了很久很久，就是因为直接continue了
                }
                //到达过state状态
                if (other.containsKey(state)){
                    //找到答案
                    return cur.get(poll)+1+other.get(state);
                }else {
                    deque.addLast(state);
                    cur.put(state,cur.get(poll)+1);
                }
            }
        }
        return -1;
    }
	//由于我是用String类型存储九宫格的，swap方法就是用来模拟空格块移动的
    public static String swap(String s,int a,int b){
        char[] sc = new char[9];
        for (int i=0;i<9;++i){
            sc[i] = s.charAt(i);
        }
        char tmp = sc[a];
        sc[a]=sc[b];
        sc[b]=tmp;
        return new String(sc);
    }
	//获取当前状态空格块的位置
    public static int getIndex(String s){
        return s.indexOf('.');
    }
}
~~~

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

大喵喵不可爱

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C++代码）

C语言程序设计教程（第三版）课后习题7.1 （C++代码）

C语言训练-求车速（C语言代码）

C二级辅导-进制转换（C语言代码）

Java版本双向BFS

评论区

精彩推荐

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

简单的a+b （C语言代码）

WU-链表数据求和操作（C++代码）

三角形（C++代码）递推

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

简单的a+b （C语言代码）

文科生的悲哀（C语言代码）

1014题解

大喵喵不可爱

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C++代码）

C语言程序设计教程（第三版）课后习题7.1 （C++代码）

C语言训练-求车速 （C语言代码）

C二级辅导-进制转换 （C语言代码）

Java版本 双向BFS

评论区

精彩推荐

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C++代码）（手动优化一下计算）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

简单的a+b （C语言代码）

WU-链表数据求和操作 （C++代码）

三角形 （C++代码）递推

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

简单的a+b （C语言代码）

文科生的悲哀 （C语言代码）

1014题解

C语言训练-求车速（C语言代码）

C二级辅导-进制转换（C语言代码）

Java版本双向BFS

　　评论区

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

WU-链表数据求和操作（C++代码）

三角形（C++代码）递推

文科生的悲哀（C语言代码）