public class Solution {
public class Element {
int direction;
int row, col;
String moves;
Element(int row, int col, String moves, int direction) {
this.row = row;
this.col = col;
this.moves = moves;
this.direction = direction;
}
}
public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
//initialization
int m = maze.length, n = maze[0].length;
Queue<Element> path = new LinkedList<>();
char[] directions = {'d', 'l', 'r', 'u'};
int[] deltaRow = {1, 0, 0, 1};
int[] deltaCol = {0, 1, 1, 0};
boolean[][][] visited = new boolean[m][n][4];
//add start point
for (int i = 0; i < 4; i++) {
int row = ball[0] + deltaRow[i], col = ball[1] + deltaCol[i];
if (row >= 0 && row < m && col >= 0 && col < n && maze[row][col] == 0) {
path.add(new Element(row, col, String.valueOf(directions[i]), i));
}
}
while (!path.isEmpty()) {
Element top = path.poll();
visited[top.row][top.col][top.direction] = true;
if (top.row == hole[0] && top.col == hole[1]) {
return top.moves;
}
//go with same direction
int nextRow = top.row + deltaRow[top.direction];
int nextCol = top.col + deltaCol[top.direction];
if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && maze[nextRow][nextCol] == 0) {
//no hit wall
if (!visited[nextRow][nextCol][top.direction]) {
path.offer(new Element(nextRow, nextCol, top.moves, top.direction));
}
} else {
//hit the wall, change direction
for (int direction = 0; direction < 4; direction++) {
if (direction != top.direction) {
nextRow = top.row + deltaRow[direction];
nextCol = top.col + deltaCol[direction];
if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && maze[nextRow][nextCol] == 0
&& !visited[nextRow][nextCol][direction]) {
path.offer(new Element(nextRow, nextCol, top.moves + directions[direction], direction));
}
}
}
}
}
return "impossible";
}
}
Java BFS solution with Queue, standard BFS 15ms(beats 85.71%)


I don't understand why your bfs solution is faster than mine. It seems my solution is more like Dijkstra's Algorithm. And it should be faster I think, but it turns out your solution is faster. Can you give me some hints about that?
public class Solution { int[][] dirs = {{1, 0}, {0, 1}, {0, 1}, {1, 0}}; char[] dirc = {'d', 'l', 'r', 'u'}; public String findShortestWay(int[][] maze, int[] ball, int[] hole) { int m = maze.length, n = maze[0].length; String minS = null; int min = Integer.MAX_VALUE; int[][] map = new int[m][n]; // min distance till this node for (int i = 0; i < m; i++) Arrays.fill(map[i], Integer.MAX_VALUE); Node start = new Node(ball[0], ball[1], 0, ""); // start point PriorityQueue<Node> q = new PriorityQueue(); q.add(start); boolean[][] vis = new boolean[m][n]; // visited nodes while (!q.isEmpty()) { // extract min, get the cur position Node cur = q.poll(); if (cur.x == hole[0] && cur.y == hole[1]) break; vis[cur.x][cur.y] = true; // try 4 dirs for (int d = 0; d < 4; d++) { int x = cur.x, y = cur.y; // start point, or get the end point while (x + dirs[d][0] < m && x + dirs[d][0] >= 0 && y + dirs[d][1] < n && y + dirs[d][1] >= 0 && maze[x + dirs[d][0]][y + dirs[d][1]] != 1) { x += dirs[d][0]; y += dirs[d][1]; if (vis[x][y]  (x == hole[0] && y == hole[1])) break; } int step = cur.step + Math.abs(x  cur.x) + Math.abs(y  cur.y); if (vis[x][y]  step > map[x][y]) continue; // update distance map[x][y] = step; // next node Node next = new Node(x, y, step, cur.route + dirc[d]); // reach the end if (x == hole[0] && y == hole[1]) { if (step == min && (minS == null  next.route.compareTo(minS) < 0)) { minS = next.route; } else if (step < min) { min = step; minS = next.route; } // if reach the end in this direction, we don't need to try other directions break; } q.add(next); } } return minS == null ? "impossible" : minS; } class Node implements Comparable<Node> { int x, y, step; String route; // a string formed by directions along the way public Node(int x, int y, int step, String route) { this.x = x; this.y = y; this.step = step; this.route = route; } public int compareTo(Node that) { return this.step  that.step; } } }

@zhugejunwei I think the complexity of the two algorithms are not easy to analyze, since it depends on the actual graph. The point is, I use standard BFS, which explores every possible path equally. If you visually think about the process(I am lazy and do not know how to draw a nice picture or simulation animation), it is like a spread when hitting the wall.
Your algorithm is brilliant btw, it is a greedy approach, Dijkstra's algorithm always choose the shortest unvisited point, but in the problem, you need to first find how far is the next node from the current node, which is not given(different from Dijkstra where the distance from point to point is given). I would imagine a simple scenario that your algorithm is slower than mine where, a simple case with no wall in the graph, the hole is 10 steps above the starting point, but first you go down for 1000 steps to hit the wall, then try to find another way. The thing is your algorithm always goes until hit the wall, so it can cause some waste, scenarios like for example, you have 8 nodes in pqueue, and the 8th node is the best answer, you explores the first 7 nodes, and they take a lot of time since they just can go straight for one direction for a long distance.
But I agree, there are scenarios that your algorithm is faster, basically the difference is DFS or BFS, for a random graph, I am not sure which one is better, I would imagine it would be similar.

@yanzhan2 Thanks for your detailed explanation. But there is one line in my solution that can simply detect the hole point when the ball is passing by:
if (vis[x][y]  (x == hole[0] && y == hole[1])) break;
. So it will not go down for 1000 steps to hit the wall, it will instead stop right away. So the example case you mentioned I think it's not a problem.Maybe it's because the comparison operation that slow this solution down? I know some operations in LeetCode are quite slow.
But anyway, I think this would not be a big problem in an interview I think.

@zhugejunwei I agree, some small operations can affect the running time a lot. But that's not what I mean though, what I thought is, you have a for loop to try the 4 directions, and following the order of d, l, r, u, and you use DFS to go into the direction until it hits the boundary. My example was, if the hole is above the starting point, and you first go down until hits the wall in the while loop, that is what I mean by 1000 steps.
