题目地址：

https://www.lintcode.com/problem/1761/description

给定一个$3\times 3$矩阵，恰好由$0\sim 8$一共$9$个数字组成，每次可以让$0$与相邻位置进行交换。再给定一个正整数$k$，问得到$[[1,2,3],[4,5,6],[7,8,0]]$需要的步数是否不超过$k$。

可以用BFS来做。代码如下：

import java.util.*;

public class Solution {
    /**
     * @param A: the initial state
     * @param k: the limit
     * @return: the steps
     */
    public String digitalHuarongRoad(int[][] A, int k) {
        // Write your code here.
        StringBuilder sb = new StringBuilder();
        for (int[] row : A) {
            for (int ch : row) {
                sb.append(ch);
            }
        }
        
        String start = sb.toString();
        if ("123456780".equals(start)) {
            return "true";
        }
        
        Queue<String> queue = new LinkedList<>();
        queue.offer(start);
        Set<String> vis = new HashSet<>();
        vis.add(start);
        int[] d = {1, 0, -1, 0, 1};
        int res = 0;
        while (!queue.isEmpty()) {
            res++;
            // 步数大于k了，返回false
            if (res > k) {
                return "false";
            }
            
            for (int i = queue.size() - 1; i >= 0; i--) {
                String cur = queue.poll();
                for (String next : getNexts(cur, vis, d)) {
                    if ("123456780".equals(next)) {
                        return "true";
                    }
                    
                    vis.add(next);
                    queue.offer(next);
                }
            }
        }
        
        return "false";
    }
    
    private Set<String> getNexts(String s, Set<String> vis, int[] d) {
        int x = 0, y = 0, old = 0;
        for (int i = 0; i < 9; i++) {
            if (s.charAt(i) == '0') {
                x = i / 3;
                y = i % 3;
                old = i;
                break;
            }
        }
        
        Set<String> set = new HashSet<>();
        char[] chs = s.toCharArray();
        for (int i = 0; i < 4; i++) {
            int nextX = x + d[i], nextY = y + d[i + 1];
            if (0 <= nextX && nextX < 3 && 0 <= nextY && nextY < 3) {
                int cur = nextX * 3 + nextY;
                swap(chs, old, cur);
                String next = new String(chs);
                if ("123456780".equals(next)) {
                    set.clear();
                    set.add(next);
                    return set;
                }
                
                if (!vis.contains(next)) {
                    set.add(next);
                }
                
                swap(chs, old, cur);
            }
        }
        
        return set;
    }
    
    private void swap(char[] s, int i, int j) {
        char tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
    }
}

时空复杂度$O(4^k)$。