C# DFS


  • 0
    H
    public bool HasPath(int[,] maze, int[] start, int[] destination) {
            Dictionary<string, bool> memo = new Dictionary<string, bool>();
            HashSet<string> visited = new HashSet<string>();
            return Recurse(memo, visited, maze, start, destination);   
        }
        
        public bool Recurse(Dictionary<string, bool> memo, HashSet<string> visited, int[,] maze, int[] start, int[] destination) {
            string key = string.Format("{0},{1}", start[0], start[1]);
            if (memo.ContainsKey(key)) return memo[key];
            if (visited.Contains(key)) return false;
            visited.Add(key); 
            
            if (start[0] == destination[0] && start[1] == destination[1]) return true;
            
            int[] dx = new int[] {1, -1, 0, 0};
            int[] dy = new int[] {0, 0, 1, -1};
            int m = maze.GetLength(0);
            int n = maze.GetLength(1);
            
            for(int i = 0; i < dx.Length; i++) {
                int nx = start[0] + dx[i];
                int ny = start[1] + dy[i];
                
                while (nx >= 0 && ny >= 0 && nx < m && ny < n && maze[nx, ny] == 0) {
                    nx = nx + dx[i];
                    ny = ny + dy[i];
                }
                
                nx = nx - dx[i];
                ny = ny - dy[i];
                
                if (nx == start[0] && ny == start[1]) continue;
                
                if (Recurse(memo, visited, maze, new int[] { nx, ny }, destination)) {
                    memo[key] = true;
                    return true;
                }
            }
            
            memo[key] = false;
            return false;
        }
    

Log in to reply
 

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