LintCode 794 Sliding Puzzle II

思路

【注意bfs中，在将一个元素加入queue中后就要标记为visited】
隐式图bfs，level-order bfs，记录步数。定义每一个节点为每一个状态（9个位置的数字），边定义为两个状态之间通过移动0一次可以得到，则二者之间有一条边。主要过程就是bfs进行层序搜索。
其中一个技巧是将二维数组转化为字符串来保存，这样方便队列操作以及查重等操作。
实现了两个函数：（1）matrixToString：将二维数组转成String；
（2）getNextState：得到下一个状态表示的字符串。在该函数中，涉及到二维数组和一维数组的下标转换问题：
（1）1D=>2D: 一维数组的下标/第一维的大小=二维数组的x；一维数组的下标%第一维的大小=二维数组的y。
（2）2D=>1D: x* 第二维大小+y=一维数组的下标
流程：首先找到‘0’的坐标，然后上下左右4个方向进行探索，用‘0’去交换。每次得到一个状态字符串，加入到结果list中，最后返回一个结果list。

代码

public class Solution {
    /*** @param init_state: the initial state of chessboard* @param final_state: the final state of chessboard* @return: return an integer, denote the number of minimum moving*/public int minMoveStep(int[][] init_state, int[][] final_state) {
    // # write your code hereString source = matrixToString(init_state);String target = matrixToString(final_state);Queue<String> queue = new LinkedList<>();Set<String> visited = new HashSet<>();queue.offer(source);visited.add(source);int step = 0;while(!queue.isEmpty()) {
    int size = queue.size();for(int i = 0; i < size; i++) {
    String cur = queue.poll();if(cur.equals(target)) return step;for(String next : getNextState(cur)) {
    if(!visited.contains(next)) {
    queue.offer(next);visited.add(next);}}}step++;}return -1;}public String matrixToString(int[][] matrix) {
    StringBuilder sb = new StringBuilder();for(int i = 0; i < 3; i++) {
    for(int j = 0; j < 3; j++) {
    sb.append(matrix[i][j]);}}return sb.toString();}public List<String> getNextState(String curState) {
    List<String> res = new ArrayList<>();int zeroIndex = curState.indexOf('0');int zx = zeroIndex / 3;int zy = zeroIndex % 3;int[] dx = {
    0, 0, 1, -1};int[] dy = {
    1, -1, 0, 0};for(int i = 0; i < 4; i++) {
    int nx = zx + dx[i];int ny = zy + dy[i];if(0 <= nx && nx < 3 && 0 <= ny && ny < 3) {
    char[] sc = curState.toCharArray();// swapsc[zx * 3 + zy] = sc[nx * 3 + ny];sc[nx * 3 + ny] = '0';res.add(new String(sc));}}return res;}
}

复杂度

时间复杂度O(n)，n为节点数，即状态数量，为9!
空间复杂度O(n+m), m为边数，为C(n, 2).
二者都可视为常数级[?]