Share my java DFS clear solution

• I failed to solve this problem during the contest, this solution I come out by referring solution from @chidong. (Thanks very much for sharing!) This is his post.

I borrowed the most of main logic part and using instance variables to cache global variables (I very like this, it makes code very clear). The differences are I used the minimal distance to map to judge if I should continue to a direction, and also a Point class and an enum to cache distance information. I think it's helpful to make my code a bit more readable.

The two helper classes contribute a bit more code, but main logic is very short.

Hope this post can help. Following is my code.

``````public class Solution {
public enum D {
UP(-1, 0, "u"),
DOWN(1, 0, "d"),
LEFT(0, -1, "l"),
RIGHT(0, 1, "r");

private D(int x, int y, String s){
this.x = x;
this.y = y;
this.s = s;
}
public final int x;
public final int y;
public final String s;
}

public class Point {
int x;
int y;
String path;
int distance;

public Point(int x, int y) {
this.x = x;
this.y = y;
this.path = "";
this.distance = 0;
}

public Point(Point p) {
this.x = p.x;
this.y = p.y;
this.path = p.path;
this.distance = p.distance;
}
}

private Point shortest;
private int[][] min;
private int tx;
private int ty;

public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
this.tx = hole[0];
this.ty = hole[1];
this.min = new int[maze.length][maze[0].length];
Point p = new Point(ball[0], ball[1]);
move(p, null, maze);
return shortest == null ? "impossible" : shortest.path;
}

public void move(Point p, D d, int[][] maze) {
if(d != null){
if(min[p.x][p.y] != 0 && p.distance > min[p.x][p.y]){
return;
}
min[p.x][p.y] = p.distance;
int x = p.x + d.x;
int y = p.y + d.y;
while(x >= 0 && x < maze.length && y >= 0 && y < maze[0].length && maze[x][y] == 0) {
p.x = x;
p.y = y;
p.distance++;
if(x == tx && y == ty) {
if(shortest == null
|| shortest.distance > p.distance
|| (shortest.distance == p.distance && shortest.path.compareTo(p.path) > 0)) {
shortest = p;
return;
}
}
x = x + d.x;
y = y + d.y;
}
}
for(D nextD : d.values()){
if(d != null) {
if((d == D.UP || d == D.DOWN) && (nextD == D.UP || nextD == D.DOWN)
|| (d == D.LEFT || d == D.RIGHT) && (nextD == D.LEFT || nextD == D.RIGHT)){
continue;
}
}
int nx = p.x + nextD.x;
int ny = p.y + nextD.y;

if(nx >= 0 && nx < maze.length && ny >= 0 && ny < maze[0].length && maze[nx][ny] == 0) {
Point nextP = new Point(p);
nextP.path += nextD.s;
move(nextP, nextD, maze);
}
}
}
}``````

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