# clear bfs java solution based on Maze II

• '''
public class Solution {

``````class Tuple implements Comparable<Tuple> {
int x;
int y;
int len;
String path;

public Tuple(int x, int y, int len, String path) {
this.x = x;
this.y = y;
this.len = len;
this.path = path;
}

@Override
public int compareTo(Tuple other) {
if (this.len == other.len) {
return this.path.compareTo(other.path);
}
return this.len - other.len;
}
}

public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
int row = maze.length;
int col = maze[0].length;
int[][] dir = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
char[] dirs = new char[]{'r', 'l', 'd', 'u'};
int[][] distance = new int[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
distance[i][j] = Integer.MAX_VALUE;
}
}
PriorityQueue<Tuple> queue = new PriorityQueue<>();
queue.offer(new Tuple(ball[0], ball[1], 0, ""));
while (!queue.isEmpty()) {
Tuple tuple = queue.poll();
if (tuple.len >= distance[tuple.x][tuple.y]) {
continue;
}
distance[tuple.x][tuple.y] = tuple.len;
for (int i = 0; i < 4; i++) {
int x = tuple.x;
int y = tuple.y;
int len = tuple.len;
while (x >= 0 && x < row && y >= 0 && y < col && maze[x][y] == 0) {
if (x == hole[0] && y == hole[1]) {
Tuple next = new Tuple(x, y, len, tuple.path);
next.path += dirs[i];
}
x += dir[i][0];
y += dir[i][1];
len++;
}
x -= dir[i][0];
y -= dir[i][1];
len--;
Tuple next = new Tuple(x, y, len, tuple.path);
next.path += dirs[i];
queue.offer(next);
}
}
Collections.sort(result);
return result.isEmpty() ? "impossible" : result.get(0).path;
}
``````

}
'''

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