private int[][] DIRECTIONS = new int[][]{{1,0}, {0,-1}, {0,1}, {-1,0}};

private char[] LETTERS = new char[]{'d', 'l', 'r', 'u'};

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[] row: distance) Arrays.fill(row, Integer.MAX_VALUE);

distance[ball[0]][ball[1]] = 0;

StringBuilder sb = new StringBuilder();

String[] res = new String[1];

int[] dis = new int[]{Integer.MAX_VALUE};

roll(maze, ball[0], ball[1], hole[0], hole[1], distance, sb, M, N, res, dis);

return res[0] == null ? "impossible" : res[0];

}

private void roll(int[][] maze, int i, int j, int hi, int hj, int[][] distance, StringBuilder sb, int M, int N, String[] res, int[] dis) {

int len = sb.length();

for (int k=0; k<4; k++) {

int[] dir = DIRECTIONS[k];

char ch = LETTERS[k];

sb.append(ch);

int x = i + dir[0];

int y = j + dir[1];

int count = 0;

while (x >= 0 && y >= 0 && x < M && y < N && maze[x][y] == 0) {

if (x == hi && y == hj) break;

x += dir[0];

y += dir[1];

count++;

}

int d = distance[i][j] + count;

if (x == hi && y == hj) {

if (d < dis[0]) {

dis[0] = d;

res[0] = sb.toString();

} else if (d == dis[0]) {

String tmp = sb.toString();

if (res[0] == null || tmp.compareTo(res[0]) < 0) {

res[0] = tmp;

}

}

sb.setLength(len);

continue;

}

x -= dir[0];

y -= dir[1];

if (d < distance[x][y]) {

distance[x][y] = d;

roll(maze, x, y, hi, hj, distance, sb, M, N, res, dis);

}

sb.setLength(len);

}

}