【BFS】 773. 滑动谜题

2024-02-14 13:12

文章标签 bfs 谜题滑动 773

本文主要是介绍【BFS】 773. 滑动谜题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

773. 滑动谜题

解题思路

首先定义了一个 slidingPuzzle 方法，接收一个二维数组 board 作为参数，表示初始的拼图板状态，然后返回一个整数表示移动到目标状态所需的最小步数。
初始化了一个二维数组 neighbor，用于记录每个数字在一维字符串中的相邻索引，这是为了在移动数字时判断合法性。
创建了一个队列 q 和一个哈希集 visited。队列用于广度优先搜索（BFS）时存储待处理的拼图板状态，哈希集用于记录已经访问过的拼图板状态，避免重复访问。
将初始的二维数组转换成一维字符串，并将其作为起始状态加入队列，并标记为已访问。
在一个循环中，不断从队列中取出拼图板状态进行处理，直到队列为空。在每一步中，先判断当前状态是否为目标状态，若是则返回步数。
若当前状态不是目标状态，则遍历每个数字的相邻索引，尝试将数字0与相邻数字交换位置，生成新的拼图板状态。
如果新状态未被访问过，则将其加入队列，并标记为已访问。
最后返回 -1，表示无法达到目标状态。

class Solution {public int slidingPuzzle(int[][] board) {int m = 2;int n = 3;StringBuilder sb = new StringBuilder();String target = "123450";// 将2 x 3数组转换为字符串 作为BFS的起点局面for(int i = 0; i < board.length; i++){for(int j = 0; j < board[0].length; j++){sb.append(board[i][j]);}}String start = sb.toString();// 记录一维字符串的相邻索引int[][] neighbor = new int[][]{{1,3},{0,4,2},{1,5},{0,4},{3,1,5},{4,2}};Queue<String> q = new LinkedList<>();// 双向链表模拟队列HashSet<String> visited = new HashSet<>();// 从起点开始搜索q.offer(start);visited.add(start);// 标记已经访问了int step = 0;while(!q.isEmpty()){int sz = q.size();for(int i = 0; i < sz; i++){String cur = q.poll();// 判断是否到达目标局面if(target.equals(cur)){return step;}// 没有到达 搜索下一种字符串局面 然后入队// 通过计算索引0 的周围索引 然后移动 判断新的字符串是否出现过// 新的字符串没有出现过  直接入队// 找到数字0的索引int id = 0;for(;cur.charAt(id) != '0'; id++);// 将数字0和相邻的数字交换位置for(int adj: neighbor[id]){// 遍历数字0 的相邻数字的索引String new_board = swap(cur.toCharArray(),adj,id);// 判断新的字符串是否已经出现过if(!visited.contains(new_board)){// 如果没有出现过  直接入队q.offer(new_board);visited.add(new_board);// 标记已经出现过}}}step++;}return -1;// 没找到 直接-1}// 交换一个字符串的两个字符private String swap(char[] chars,int i,int j){char temp = chars[i];chars[i] = chars[j];chars[j] = temp;return new String(chars);}
}