My solution takes me 4 hours.... Thanks for my insistence...

class Solution { public String findShortestWay(int[][] maze, int[] ball, int[] hole) { Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[]{ball[0], ball[1]}); int m = maze.length, n = maze[0].length; int[][] dir = new int[][]{{1, -1, 0, 0}, {0, 0, 1, -1}}; String[] pa = new String[]{"d", "u", "r", "l"}; int[][] dp = new int[m][n]; String[][] dpPath = new String[m][n]; for (int[] d: dp) { Arrays.fill(d, Integer.MAX_VALUE); } for (String[] d: dpPath) { Arrays.fill(d, "z"); } dp[ball[0]][ball[1]] = 0; dpPath[ball[0]][ball[1]] = ""; while (!queue.isEmpty()) { int[] cur = queue.poll(); for (int i = 0; i < 4; i++) { int row = cur[0]; int col = cur[1]; String path = dpPath[row][col]; int dist = dp[row][col]; path += pa[i]; while (row >= 0 && row < m && col >= 0 && col < n && maze[row][col] != 1) { if (row == hole[0] && col == hole[1]) { break; } row += dir[0][i]; col += dir[1][i]; dist++; } if (row != hole[0] || col != hole[1]) { row -= dir[0][i]; col -= dir[1][i]; dist--; } if (row == cur[0] && col == cur[1]) { continue; } if (dist <= dp[row][col]) { if (dist < dp[row][col]) { dp[row][col] = dist; dpPath[row][col] = path; } else if (path.compareTo(dpPath[row][col]) < 0) { dpPath[row][col] = path; } queue.offer(new int[]{row, col}); } } } return dpPath[hole[0]][hole[1]].equals("z")? "impossible": dpPath[hole[0]][hole[1]]; } }The Maze III