490. The Maze

class Solution {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        int m = maze.length, n = maze[0].length;
        memo = new Boolean[m][n];
        int i = start[0], j = start[1];
        return dfs(maze, new boolean[m][n], i, j, destination);
    }

    Boolean[][] memo;

    boolean dfs(int[][] maze, boolean[][] visited, int i, int j, int[] destination)
    {
        if(destination[0] == i && destination[1] == j) return true;
        if(memo[i][j] != null) return memo[i][j];
        int[] dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
        int m = maze.length, n = maze[0].length;
        visited[i][j] = true;
        for(int k = 0; k < 4; k++)
        {
            int ni = i, nj = j;
            while(ni + dx[k] >= 0 && nj + dy[k]>= 0 && ni + dx[k] < m && nj + dy[k]< n && maze[ni + dx[k]][nj + dy[k]] == 0)
            {
                ni += dx[k];
                nj += dy[k];
            }
            // now ni and nj are at border
            if(ni == i && nj == j || visited[ni][nj]) continue;    // did not change position
            visited[ni][nj] = true;
            if(dfs(maze, visited, ni, nj, destination)) return memo[i][j] = true;
            visited[ni][nj] = false;
        }
        return memo[i][j] = false;
    }
}