@vinod23

My dfs solution just got accepted.

Share my code and comments:

// dfs solution
class Solution {
private int[] dr;
private int[] dc;
private int[][] MAZE;
private int R;
private int C;
private int[] dest;
private boolean res;
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
dr = new int[]{-1, 1, 0, 0}; // u d l r
dc = new int[]{0, 0, -1, 1}; // u d l r
MAZE = maze;
R = maze.length;
C = maze[0].length;
dest = destination;
res = false;
// doesn't care the initial direction parameter
dfs(-1, start, new boolean[R][C]);
return res;
}
private void dfs(int dir, int[] start, boolean[][] visited) {
int r = start[0], c = start[1];
if (Arrays.equals(start, dest)) {
res = true;
return;
}
if (visited[r][c]) return;
visited[r][c] = true;
// up down left right
for (int i = 0; i < 4; ++i) {
if (i == dir) continue; // skip the direction that will hit the wall again
int x = r, y = c;
while (isValid(new int[]{x + dr[i], y + dc[i]})) {
x += dr[i];
y += dc[i];
}
dfs(i, new int[]{x, y}, visited);
}
}
// return true if the coord is valid and maze[coord] == 0;
private boolean isValid(int[] coord) {
int r = coord[0];
int c = coord[1];
if (r < 0 || r >= R || c < 0 || c >= C) return false;
if (MAZE[r][c] == 1) return false;
return true;
}
}