1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

class Solution {
    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        int m = maze.length;
        int n = maze[0].length;

        int[][] distance = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(distance[i], Integer.MAX_VALUE);
        }

        Map<Integer, String> map = new HashMap<>();
        for (int i = 0; i < m * n; i++) {
            map.put(i, "");
        }

        distance[ball[0]][ball[1]] = 0;
        dfs(maze, distance, map, ball[0], ball[1], hole);

        String res = map.get(hole[0] * n + hole[1]);
        return res.equals("") ? "impossible" : res;
    }

    private static void dfs(int[][] maze, int[][] distance, Map<Integer, String> map, int x, int y, int[] hole) {
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        String[] actions = {"u", "d", "l", "r"};

        int m = maze.length;
        int n = maze[0].length;

        for (int i = 0; i < 4; i++) {
            int nextX = x;
            int nextY = y;
            int stepCnt = 0;

            String path = map.get(x * n + y);

            while (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && maze[nextX][nextY] == 0
                    && !(nextX == hole[0] && nextY == hole[1])) {
                nextX += dirs[i][0];
                nextY += dirs[i][1];
                stepCnt++;
            }

            if (nextX != hole[0] || hole[1] != nextY) {
                nextX -= dirs[i][0];
                nextY -= dirs[i][1];
                stepCnt--;
            }

            path += actions[i];

            if (distance[nextX][nextY] > distance[x][y] + stepCnt) {
                distance[nextX][nextY] = distance[x][y] + stepCnt;
                map.put(nextX * n + nextY, path);
                if (nextX != hole[0] || nextY != hole[1]) {
                    dfs(maze, distance, map, nextX, nextY, hole);
                }
            } else if (distance[nextX][nextY] == distance[x][y] + stepCnt && path.compareTo(map.get(nextX * n + nextY)) < 0) {
                map.put(nextX * n + nextY, path);
                if (nextX != hole[0] || nextY != hole[1]) {
                    dfs(maze, distance, map, nextX, nextY, hole);
                }
            }
        }
    }
}