# Easy understanding BFS Java solution

• ``````public class Solution {
private int[][] dir = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
private char[] alph = {'d', 'l', 'r', 'u'};
// dlru {1, 0}, {0, -1}, {0, 1}, {-1, 0}

public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
if (maze == null || maze.length == 0 || maze[0].length == 0) {
return "";
}
int n = maze.length, m = maze[0].length;
queue.offer(ball);
String[][] path = new String[n][m];
int[][] step = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
step[i][j] = Integer.MAX_VALUE;
path[i][j] = "";   //!!!
}
}
step[ball[0]][ball[1]] = 0;

while (!queue.isEmpty()) {
int[] point = queue.poll();
for (int i = 0; i < 4; i++) {
int[] d = dir[i];
int x = point[0];
int y = point[1];
if (x == hole[0] && y == hole[1]) {
break;
}
while (x + d[0] >= 0 && x + d[0] < n && y + d[1] >= 0 && y + d[1] < m && maze[x + d[0]][y + d[1]] == 0) {
x += d[0];
y += d[1];
if (x == hole[0] && y == hole[1]) {
break;
}
}
int curStep = Math.abs(x - point[0]) + Math.abs(y - point[1]);
if (curStep == 0) {
continue;
}
if (step[x][y] > curStep + step[point[0]][point[1]]) {
// update step & path, and put point into queue
step[x][y] = curStep + step[point[0]][point[1]];
path[x][y] = path[point[0]][point[1]] + alph[i];
queue.offer(new int[]{x, y});
} else if (step[x][y] == curStep + step[point[0]][point[1]]) {
// compare path and update path
String curPath = path[point[0]][point[1]] + alph[i];
path[x][y] = comparePath(curPath, path[x][y]);
queue.offer(new int[]{x, y});
}
}
}
return step[hole[0]][hole[1]] == Integer.MAX_VALUE? "impossible" : path[hole[0]][hole[1]];
}

private String comparePath(String s1, String s2) {
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
int len = Math.min(c1.length, c2.length);
for (int i = 0; i < len; i++) {
if (c1[i] < c2[i]) {
return s1;
}
if (c1[i] > c2[i]) {
return s2;
}
}
return len == c1.length ? s1 : s2;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.