# Similar to The Maze II. Easy-understanding Java bfs solution.

• We just need to implement `Comparable` of `Point`, and record the route of every point.

``````public class Solution {
class Point implements Comparable<Point> {
int x,y,l;
String s;
public Point(int _x, int _y) {x=_x;y=_y;l=Integer.MAX_VALUE;s="";}
public Point(int _x, int _y, int _l,String _s) {x=_x;y=_y;l=_l;s=_s;}
public int compareTo(Point p) {return l==p.l?s.compareTo(p.s):l-p.l;}
}
public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
int m=maze.length, n=maze[0].length;
Point[][] points=new Point[m][n];
for (int i=0;i<m*n;i++) points[i/n][i%n]=new Point(i/n, i%n);
int[][] dir=new int[][] {{-1,0},{0,1},{1,0},{0,-1}};
String[] ds=new String[] {"u","r","d","l"};
PriorityQueue<Point> list=new PriorityQueue<>(); // using priority queue
list.offer(new Point(ball[0], ball[1], 0, ""));
while (!list.isEmpty()) {
Point p=list.poll();
if (points[p.x][p.y].compareTo(p)<=0) continue; // if we have already found a route shorter
points[p.x][p.y]=p;
for (int i=0;i<4;i++) {
int xx=p.x, yy=p.y, l=p.l;
while (xx>=0 && xx<m && yy>=0 && yy<n && maze[xx][yy]==0 && (xx!=hole[0] || yy!=hole[1])) {
xx+=dir[i][0];
yy+=dir[i][1];
l++;
}
if (xx!=hole[0] || yy!=hole[1]) { // check the hole
xx-=dir[i][0];
yy-=dir[i][1];
l--;
}
list.offer(new Point(xx, yy, l, p.s+ds[i]));
}
}
return points[hole[0]][hole[1]].l==Integer.MAX_VALUE?"impossible":points[hole[0]][hole[1]].s;
}
}
``````

• BFS:

1. Start from `ball`, adding 4 directions of it into queue(order by D->L->R->U), if it is not boundary or `1`.
2. Poll one path from queue while the queue has path:
...a) if the path reach hole, return the path.
...c) If the next cell on the direction is boundary or `1`, adding other two directions into queue.
``````  public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
if(maze.length == 0) return "";
int m = maze.length, n = maze[0].length;

int bx = ball[0], by = ball[1];
if(!isTurn(maze, bx + 1, by)) q.offer(new Cell(bx + 1, by, "d"));
turnLeftRight(q, maze, bx, by, "");
if(!isTurn(maze, bx - 1, by)) q.offer(new Cell(bx - 1, by, "u"));

while(!q.isEmpty()){
Cell c = q.poll();
if(c.x == hole[0] && c.y == hole[1]) return c.path;
char d = c.path.charAt(c.path.length() - 1);

switch(d){
case 'd':
if(!isTurn(maze, c.x + 1, c.y)){
q.offer(new Cell(c.x + 1, c.y, c.path));
} else {
if(maze[c.x][c.y] == -1) continue;
maze[c.x][c.y] = -1;
turnLeftRight(q, maze, c.x, c.y, c.path);
}
break;
case 'l':
if(!isTurn(maze, c.x, c.y - 1)){
q.offer(new Cell(c.x, c.y - 1, c.path));
} else {
if(maze[c.x][c.y] == -1) continue;
maze[c.x][c.y] = -1;
turnUpDown(q, maze, c.x, c.y, c.path);
}
break;
case 'r':
if(!isTurn(maze, c.x, c.y + 1)){
q.offer(new Cell(c.x, c.y + 1, c.path));
} else {
if(maze[c.x][c.y] == -1) continue;
maze[c.x][c.y] = -1;
turnUpDown(q, maze, c.x, c.y, c.path);
}
break;
case 'u':
if(!isTurn(maze, c.x - 1, c.y)){
q.offer(new Cell(c.x - 1, c.y, c.path));
} else {
if(maze[c.x][c.y] == -1) continue;
maze[c.x][c.y] = -1;
turnLeftRight(q, maze, c.x, c.y, c.path);
}
break;
}
}
return "impossible";
}

void turnLeftRight(Queue<Cell> q, int[][] maze, int x, int y, String path){
if(!isTurn(maze, x, y - 1)) q.offer(new Cell(x, y - 1, path + "l"));
if(!isTurn(maze, x, y + 1)) q.offer(new Cell(x, y + 1, path + "r"));
}

void turnUpDown(Queue<Cell> q, int[][] maze, int x, int y, String path){
if(!isTurn(maze, x + 1, y)) q.offer(new Cell(x + 1, y, path + "d"));
if(!isTurn(maze, x - 1, y)) q.offer(new Cell(x - 1, y, path + "u"));
}

boolean isTurn(int[][] maze, int x, int y){
return x < 0 || x >= maze.length || y < 0 || y >= maze[0].length || maze[x][y] == 1;
}

class Cell{
int x, y;
String path;
public Cell(int xx, int yy, String p){
x = xx;
y = yy;
path = p;
}
}``````

• @ckcz123 What is the time complexity of the algorithm .Is it O(n^2) ?

• Hey @ckcz123 Since these questions are now locked and available in premium I want to solve them now Could you help me on this and tell me what are all the 3 questions on maze exactly ?

• @anirudhkowdeed
Since it's very similar to Dijkstra
points: any stoppable points and start point
edges = any possible path between two points

I think it will be O((edges + points) * O(points))

• how do you ensure that it is the lexicographically smallest? @ckcz123

• This post is deleted!

• @jyu332
The compareTo in the constructor makes sure that each path stored in lexicographically smallest when the lengths are same

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

``````class Solution {
public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
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]];
}
}
``````

• It is not necessary to use a PriorityQueue. By all means, you cannot stop searching once the hole is reached, as the local optimum may not be a global optimum here. A point that is marked as "explored" in Dijkstra's algorithm is not completely "explored" as there might be another path that reaches this with equal distance but with a smaller lexicographical order (i.e., "ul" vs. "lu"). So anyway, you have to search all the possible paths that can reach the hole. So using a normal queue would suffice.

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