Java DFS with some optimization, 162ms

• Guys, if we add a "from" int variable, to avoid going back to the direction where we came from, it can save several hundred ms.
like this code below. The running time is 162ms

``````class Solution {
private int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}};

public int shortestDistance(int[][] maze, int[] start, int[] destination) {
int[][] visited = new int[maze.length][maze[0].length];
findDistance(maze, start, destination, 0, visited, 10);
return visited[destination[0]][destination[1]] == 0 ? -1 : visited[destination[0]][destination[1]];
}

private void findDistance(int[][] maze, int[] start, int[] destination, int curDist, int[][] visited, int from) {
if (visited[start[0]][start[1]] != 0 && visited[start[0]][start[1]] <= curDist) {
return;
}
visited[start[0]][start[1]] = curDist;
if (Arrays.equals(start, destination)) {
return;
}
int cantGo = from % 2 == 1 ? from - 1 : from + 1;
//try to roll in all four direction
for (int i = 0; i < 4; i++) {
if (i == cantGo) {
continue;
}
int newDist = curDist;
int x = start[0];
int y = start[1];
while (canRoll(maze,x, y, i)) {
x += dir[i][0];
y += dir[i][1];
newDist++;
}
if (start[0] != x ||start[1] != y) {
findDistance(maze, new int[]{x,y}, destination, newDist, visited, i);
}
}
}

private boolean canRoll(int[][] maze, int x, int y, int i) {
x += dir[i][0];
y += dir[i][1];
boolean canRoll = (x >= 0 && x < maze.length && y >= 0 && y < maze[0].length && maze[x][y] != 1);
return canRoll;
}
//Time complexity: O(n * m)
//Space complexity: O(n * m)
}
``````

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