小米笔试10.19

唉π_π，10月底还在做笔试
选择题25个：图论+二叉树+dp
编程两个：两个搜索题。
题1：数独
public class Main {

    private static int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int T = in.nextInt();
while(T-->0){
            int[][] map = new int[3][3];
            boolean[] vis = new boolean[10];
            for(int i=0;i<3;i++){
                for(int j=0;j<3;j++){
                    map[i][j] = in.nextInt();
                    vis[map[i][j]] = true;
                }
            }

            long ans = dfs(0,map,vis);
            System.out.println(ans);

        }

    }

    private static long dfs(int i, int[][] map, boolean[] vis){

        if(i == 9){
            return 1L;
        }

        int x = i/3;
        int y = i%3;
        if(map[x][y] != 0){
            if(check(x,y,map)){
                return dfs(i+1,map,vis);
            }else{
                return 0L;
            }
        }
        long ret = 0;
        for(int j=1;j<=9;j++){
            if(vis[j]){
                continue;
            }
            vis[j] = true;
            map[x][y] = j;
            if(check(x,y,map)){
                ret += dfs(i+1,map,vis);
            }
            map[x][y] = 0;
            vis[j] = false;

        }
        return ret;
    }

    private static boolean check(int i, int j, int[][] map){
        boolean ret = true;
        for(int[] d : dirs){
            int nx = i+d[0];
            int ny = j+d[1];
            if(nx<0 || nx>=3 || ny<0 || ny>=3 || map[nx][ny] == 0){
                continue;
            }
            if (Math.abs(map[i][j] - map[nx][ny]) == 1) {
                ret = false;
                break;
            }
        }
        return ret;
    }

}

题2：感觉数据比较弱，居然过了，笑死
public class Main {
    
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int a = in.nextInt();
        int b = in.nextInt();

        int[] vis = new int[b * 10 + 1];
        Arrays.fill(vis, Integer.MAX_VALUE);
        dfs(b, 0, vis, a);
        if (vis[1] == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(vis[1]);
        }

    }

    private static void dfs(int x, int step, int[] vis, int a) {

        if (x == 1) {
            vis[1] = Math.min(vis[1], step);
            return;
        }
        if (vis[x] != Integer.MAX_VALUE && vis[x] <= step) {
            return;
        }
        if (x % a == 0) {
            vis[x] = step;
            dfs(x / a, step + 1, vis, a);
        }
        if (x % 10 != 0) {
            int nx = f(x);
            vis[x] = step;
            dfs(nx, step + 1, vis, a);
        }
    }

    private static int f(int x) {

        int ret = 0;
        int i = 1;
while (x >= 10) {
            int r = x % 10;
            x /= 10;
            ret += i * r;
            i *= 10;
        }

        return ret * 10 + x;
    }
}