第三道算法题——科大讯飞2023届秋招研发类笔试试卷A（三）

题：迷宫探宝，求最短距离。4×4个格子地图（1为墙，0为路，8为宝藏），由多个地图路口。 

import java.util.*;


class Point {
    int x;
    int y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}


class Main {

    static ArrayList<ArrayList<Point>> loads = new ArrayList<>();
    static int[][] direction = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

    public static void main(String[] args) {
        int[][] maze = {{0, 1, 1, 1}, {0, 0, 0, 1}, {1, 0, 8, 1}, {1, 0, 1, 1}};
        ArrayList<Point> result = winMazeGift(maze);
        System.out.println(result.size());
    }


    public static ArrayList<Point> winMazeGift(int[][] maze) {
        // write code here
        boolean[][] visited = new boolean[4][4];
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (maze[i][j] == 1) visited[i][j] = true;
            }
        }

        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if ((i == 0 || i == 3 || j == 0 || j == 3) && maze[i][j] == 0) {
                    subWinMazeGift(maze, i, j, visited, new ArrayList<Point>());
                }
            }
        }
        ArrayList<Point> s = loads.get(0);
        for (ArrayList<Point> temp : loads) {
            if (s.size() > temp.size()) {
                s = temp;
            }
        }
        return s;
    }


    public static void subWinMazeGift(int[][] maze, int r, int c, boolean[][] visited, ArrayList<Point> load) {
        visited[r][c] = true;
        Point p = new Point(r, c);
        load.add(p);
        if (maze[r][c] == 8) {
            loads.add(new ArrayList<Point>(load));
        }else{
            for (int[] dir : direction) {
                int new_r = r + dir[0];
                int new_c = c + dir[1];
                if (new_r >= 0 && new_r < 4 && new_c >= 0 && new_c < 4 && maze[new_r][new_c] != 1 && !visited[new_r][new_c]) {
                    subWinMazeGift(maze, new_r, new_c, visited, load);
                }
            }
        }
        load.remove(p);
        visited[r][c] = false;
    }
}