// Be careful of the lexicographical sequence: d, l, r, u.
    private static final int[][] DIRS = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};

    private String shortestPath = "";

    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        String path = "";
        int[][] dist = new int[maze.length][maze[0].length];
        dist[ball[0]][ball[1]] = 1;
        dfs(ball[0], ball[1], hole, maze, dist, "");
        return shortestPath.equals("")? "impossible": shortestPath;
    }

    private void dfs(int row, int col, int[] hole, int[][] maze, int[][] dist, String curPath) {
        int m = maze.length, n = maze[0].length;
        for (int d = 0; d < 4; d ++) {
            int i = row, j = col, p = DIRS[d][0], q = DIRS[d][1], len = dist[row][col];
            while (i + p >= 0 && i + p < m && j + q >= 0 && j + q < n && maze[i + p][j + q] == 0) {
                i += p;
                j += q;
                len ++;
                if (i == hole[0] && j == hole[1] && (dist[i][j] == 0 || len <= dist[i][j])) {
                    if(len < dist[i][j] || isShorterPath(curPath, shortestPath)) {
                        shortestPath = curPath + getDir(p, q);
                        dist[i][j] = len;
                    }
                    return;
                }
            }
            if (dist[i][j] > 0 && len >= dist[i][j]) {
                continue;
            }
            dist[i][j] = len;
            dfs(i, j, hole, maze, dist, curPath + getDir(p, q));
        }
    }

    private boolean isShorterPath(String curPath, String shortestPath) {
        if(shortestPath.equals("")) {
            return true;
        }
        for(int i = 0; i < curPath.length() && i < shortestPath.length(); i ++) {
            if(curPath.charAt(i) < shortestPath.charAt(i)) {
                return true;
            }else if(curPath.charAt(i) > shortestPath.charAt(i)) {
                return false;
            }
        }
        return curPath.length() < shortestPath.length();
    }

    private String getDir(int p, int q) {
        if(p == 0 && q == 1) {
            return "r";
        }else if(p == 0 && q == -1) {
            return "l";
        }else if(p == 1 && q == 0) {
            return "d";
        }else {
            return "u";
        }
    }