# Clear Java Accepted DFS Solution with Explanation

• ``````public class Solution {
int min; //min distance to hole
String minS; //min distance's path string
int[] hole;
int[][] maze;
int[][] map; //shortest distant traveling from ball to this point
int[][] dirs = {{0,1},{-1,0},{1,0},{0,-1}}; //r, u, d, l
public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
this.min = Integer.MAX_VALUE;
this.minS = null;
this.hole = hole;
this.maze = maze;
this.map = new int[maze.length][maze[0].length];
for(int i = 0; i<map.length; i++) Arrays.fill(map[i], Integer.MAX_VALUE);

move(ball[0], ball[1], 0, "", -1);
return (minS==null) ? "impossible" : minS;
}

private void move(int r, int c, int cnt, String path, int dir){//dir is a index of dirs
if(cnt > min || cnt > map[r][c]) return; //not a shortest route for sure
if(dir!=-1){//if not from start point
if(dir==0) path+='r';
else if(dir==1) path+='u';
else if(dir==2) path+='d';
else path+='l';

//roll along dir
while(r>=0 && r<maze.length && c>=0 && c<maze[0].length && maze[r][c]==0){
map[r][c] = Math.min(map[r][c], cnt);
if(r==hole[0] && c==hole[1]){//check hole
if(cnt==min && path.compareTo(minS)<0){
minS=path;
}else if(cnt<min){
min = cnt;
minS = path;
}
return;
}
r += dirs[dir][0];
c += dirs[dir][1];
cnt++;
}
r -= dirs[dir][0];//[r,c] is wall, need to walk back 1 step
c -= dirs[dir][1];
cnt--;
}

//hit wall (or start) -> try to turn
for(int i = 0; i<dirs.length; i++){
if(dir == i) continue;//dont keep going
if(dir == (3-i)) continue;//dont go back
int newR = r + dirs[i][0];
int newC = c + dirs[i][1];
if(newR>=0 && newR<maze.length && newC>=0 && newC<maze[0].length && maze[newR][newC]==0){//can go
move(r, c, cnt, path, i);
}
}
}
}
``````

Each time, first add the direction to the path, and then go with that direction, checking for hole along the way. When hit a wall, try to turn, and go with the new direction. For the starting point, don't "go", jump directly to "turn" part.

• Thanks for your code. It's really very clear and easy to read.

• Nice code. Here is my DFS solution.

``````public class Solution {
int minStep;
int m, n;
String res;
int[][] dirs = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
String[] dirc = {"d", "r", "l", "u"}; // 0123
public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
this.m = maze.length;
this.n = maze[0].length;
this.minStep = Integer.MAX_VALUE;
this.res = null;
boolean[][] vis = new boolean[m][n];
vis[ball[0]][ball[1]] = true;

dfs(ball[0], ball[1], maze, hole, vis, "", 0);

return res == null ? "impossible" : res;
}

private void dfs(int i, int j, int[][] maze, int[] hole, boolean[][] vis, String route, int step) {
if (step > minStep) return;
if (i == hole[0] && j == hole[1]) {
if (step == minStep && route.compareTo(res) < 0) {
res = route;
} else if (step < minStep) {
minStep = step;
res = route;
}
vis[i][j] = false;
return;
}

for (int d = 0; d < 4; d++) {
// roll to the wall
int x = i, y = j;
while (x + dirs[d][0] >= 0 && x + dirs[d][0] < m && y + dirs[d][1] >= 0 && y + dirs[d][1] < n
&& maze[x + dirs[d][0]][y + dirs[d][1]] != 1) {
x += dirs[d][0];
y += dirs[d][1];
if (x == hole[0] && y == hole[1] || vis[x][y])  break;
}
if (!vis[x][y] && maze[x][y] == 0) {
vis[x][y] = true;
dfs(x, y, maze, hole, vis, route + dirc[d], step + Math.abs(x - i) + Math.abs(y - j));
vis[x][y] = false;
}
}
}
}
``````

• I really appreciated your `int[][] map` and use index of `int[][] dirs` to represent `r,u,l,d`, it simplified many works for me.

Below is my BFS solution.

But I am curious about why BFS is slower than DFS, I think this BFS solution is similar with Dijkstra's algorithm, it cannot be that slow theoretically speaking. Can you give me some hints, or maybe my implementation is not good enough to speed this BFS solution up?

Ignore what I just said... This dame line slow my solution `System.out.println(next.route);`. Actually we can see the outputs from this line, that there are much less outputs by BFS solution.

``````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();

boolean[][] vis = new boolean[m][n]; // visited nodes
while (!q.isEmpty()) {
// extract min, get the cur position
Node cur = q.poll();
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]);

// System.out.println(next.route);  /// this damn line!!! slowed my solution...

// 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;
}

}
}
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 boolean equals(Node a, Node b) {
return a.x == b.x && a.y == b.y;
}

public int compareTo(Node that) {
return this.step - that.step;
}
}
}
``````

• @zhugejunwei
I liked your dfs solution, seems easier to understand to me.

But I think there is something not that "correct" in your algorithm.
If you change your code in the for loop instead of "d from 0 to 3", but "d from 3 to 0", you will get a incorrect result.
Luckily, you choose the right sequence of the direction array for all test cases. However, the best way would be "d, l, r, u" since they increase in the sequence.

Moreover, if you have the right sequence, you won't need to compare the path for the same steps. You will always find the shortest one first.

correct me if I am wrong on this point, thanks

• @notturno Actually that's not something you said luck.... I iterate in that specific order on purpose, so that I can output the route in a right order.

There is no such luck I have ever met in this kind of question.

And don't rely on luck, dude.

• This post is deleted!

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