bfs-最小步数问题

最小步长模型

• 特征：

  主要是解决权值为1且状态为字符串类型的最短路问题，实质上是有向图的最短路问题，可以简化为bfs求最短路问题。

• 代表题目：

  • acwing 845 八数码问题：

    

    八数码题中由于每次交换的状态是由x进行上下左右移动，采用直接对x的位置进行四个方向枚举，每次求出来x的位置，需要将原字符串的位置转换为 3 * 3 矩阵中的坐标，在四个方向上进行交换x的坐标，每次记录当前状态到起点状态的步数 + 1即可，细节见代码，本题最重要的是学会字符串与二维矩阵之间的坐标转换。

    import java.util.*;public class Main {// 定义四个移动方向：上、下、左、右static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// 获取字符串中 'x' 的索引public static int get(String t) {for (int i = 0; i < t.length(); i++) {if (t.charAt(i) == 'x') {return i;}}return -1; // 理论上不会到达}// 交换字符串 t 中索引 k 和 j 的字符，返回新字符串public static String swap(String t, int k, int j) {char[] arr = t.toCharArray();char temp = arr[k];arr[k] = arr[j];arr[j] = temp;return new String(arr);}// BFS 求解从 start 到 end 的最小移动次数public static int bfs(String start, String end) {// 距离映射：记录每个状态的步数Map<String, Integer> dist = new HashMap<>();// 队列：存储待探索的状态Queue<String> q = new LinkedList<>();q.offer(start);dist.put(start, 0);while (!q.isEmpty()) {String t = q.poll();// 如果当前状态是目标状态，返回步数if (t.equals(end)) {return dist.get(t);}// 找到 'x' 的索引int k = get(t);// 计算 'x' 在 3x3 网格中的坐标int x = k / 3, y = k % 3;// 尝试四个方向移动for (int[] dir : dirs) {int nx = x + dir[0];int ny = y + dir[1];// 检查新坐标是否越界if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) {continue;}// 计算新位置的索引int newIdx = nx * 3 + ny;// 生成新状态String next = swap(t, k, newIdx);// 如果新状态未访问过，加入队列if (!dist.containsKey(next)) {dist.put(next, dist.get(t) + 1);q.offer(next);}}}// 无法到达目标状态return -1;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String start = "";for(int i = 0; i < 9; i++) start += sc.next();String end = "12345678x";int res = bfs(start, end);System.out.println(res);}
    }
    

---

• 题目2：acwing 1107 魔版 温馨提示代码又臭又长 hhh

  

思路很简单，初始状态和结束状态都已知，要求解最小步数和字典序最小的操作序列，也就是在上个题目的基础上，在bfs的时候要记录当前层的状态是由上一层的哪个状态，通过哪种方式进行转换得到的，所以需要记录路径，根据分析可知，需要用一个哈希表存储，key为当前状态，value需要涵盖上一个状态(String)和操作(char) ，所以这里的map类型为<String, PII>,具体见代码。记录完毕这个路径以后，要获得正序的操作数，需要遍历存储的pre，然后再倒序输出即可，思路不难，代码很长。。

import java.util.*;public class Main {static Map<String, Integer> dist = new HashMap<>(); // 记录当前状态距离初始状态的步数static Map<String,PII> pre = new HashMap<>(); // 存储当前状态由那个状态的哪个操作进行转移过来static char[][] g = new char[2][4];// 将字符串转换为二维矩阵存储public static void set(String t) {for(int i = 0; i < 4; i++) g[0][i] = t.charAt(i);for(int i = 0; i < 4; i++) g[1][i] = t.charAt(7 - i);}// 将二维矩阵转换为字符串public static String get() {String res = "";for(int i = 0; i < 4; i++) res += g[0][i];for(int i = 0; i < 4; i++) res += g[1][3 - i];return res;}// 操作A 交换上下两行public static String moveA(String t) {set(t);char[] temp = new char[4];for(int i = 0; i < 4; i++) {temp[i] = g[0][i];g[0][i] = g[1][i];g[1][i] = temp[i];}return get();}// 操作B 将最右边的一列插入到最左边；public static String moveB(String t) {set(t);char a = g[0][3];char b = g[1][3];for(int i = 3; i >= 1; i--) {g[0][i] = g[0][i - 1];g[1][i] = g[1][i - 1];}g[0][0] = a;g[1][0] = b;return get();}// 操作C 魔板中央对的4个数作顺时针旋转。public static String moveC(String t) {set(t);char a = g[0][1];char b = g[0][2];char c = g[1][1];char d = g[1][2];g[0][1] = c;g[0][2] = a;g[1][1] = d;g[1][2] = b;return get();}public static int bfs(String start, String end) {if(start.equals(end)) return 0;Queue<String> q = new LinkedList<>();q.offer(start);dist.put(start, 0);//  bfs遍历框架while(!q.isEmpty()){String t = q.poll();// 三种操作String[] m = new String[3];m[0] = moveA(t);m[1] = moveB(t);m[2] = moveC(t);for(int i = 0; i < 3; i++) {if(dist.containsKey(m[i])) continue; // 当前的状态被遍历过了 dist.put(m[i], dist.get(t) + 1);// 存储下一个状态由哪个状态+操作进行转移if(pre.containsKey(m[i])) continue;pre.put(m[i], new PII((char) ('A' + i), t));q.offer(m[i]);if(m[i].equals(end)) return dist.get(end);}}return -1;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String start = "12345678";String end = "";for(int i = 0; i < 8; i++) {end += sc.nextInt();}int step = bfs(start, end);System.out.println(step);// 遍历统计途中的最优解方案String res = "";String ans = end;while(!ans.equals(start)) {res += pre.get(ans).opera;ans = pre.get(ans).str;}for(int i = res.length() - 1; i >= 0; i--) System.out.print(res.charAt(i));}
}class PII {char opera; //  操作 String str; // 状态public PII(char opera, String str) {this.opera = opera;this.str = str;}
}

---

• 题目3： leetcode 752 打开转盘锁

  

本题的思路跟上面两题类似，不同点在于多了一个限制条件： deadends,也就是说在bfs的时候如果新得到的状态存在与deadends，则不会继续更新，也就是不会将当前的状态与初始状态连接；此外，每次操作相当于是对四位字符中的一位进行+1/-1操作，因为转盘是圆的，这里需要 + 10 % 10 的操作。

class Solution {static Set<String> lock = new HashSet<>();public static int bfs(String start, String end) {Queue<String> q = new LinkedList<>();Map<String, Integer> dist = new HashMap<>();q.offer(start);dist.put(start, 0);while(!q.isEmpty()) {String t = q.poll();if(t.equals(end)) return dist.get(t);StringBuilder sb = new StringBuilder();for(int i = 0; i < 4; i++) {String s1 = t.substring(0, i);String s2 = t.substring(i + 1, 4);for(int j = -1; j <= 1; j += 2) {int c = (t.charAt(i) - '0' + j + 10) % 10 ;String newStr = s1 + c + s2;if(lock.contains(newStr)) continue;if(dist.containsKey(newStr)) continue;dist.put(newStr, dist.get(t) + 1);q.offer(newStr);}}}return -1;}public int openLock(String[] deadends, String target) {lock.clear();String start = "0000";// 特判起点等于终点if(start.equals(target)) return 0;// 特判起点为不可走for(int i = 0; i < deadends.length; i++) {String t = deadends[i];lock.add(t);}if(lock.contains(start)) return -1;int ans = bfs(start, target);return ans;}
}