Simple DFS solution, beat 97%


  • 4

    Simple DFS solution
    Logic:
    the ball can roll four directions. If visited, marked as visited.

    public class Solution {
        public boolean hasPath(int[][] maze, int[] start, int[] destination) {
            // dfs
            if (maze == null || start == null || destination == null) {
                return false;
            }
            boolean[][] visited = new boolean[maze.length][maze[0].length];
            return hasPath(maze, start, destination, visited);
        }
        private boolean hasPath(int[][] maze, int[] start, int[] dest, boolean[][] visited) {
            int y = start[0];
            int x = start[1];
            if (visited[y][x]) return false;
            visited[y][x] = true;
            if (x == dest[1] && y == dest[0]) {
                return true;
            }
            // left
            if (x > 0 && maze[y][x-1] != 1) {
                int i = x - 1;
                while (i > 0 && maze[y][i-1] != 1) i--;
                if (hasPath(maze, new int[]{y, i}, dest, visited)) return true;
            }
            //right
            if (x < maze[0].length - 1 && maze[y][x+1] != 1) {
                int i = x + 1;
                while (i < maze[0].length-1 && maze[y][i+1] != 1)  i++;
                if (hasPath(maze, new int[]{y, i}, dest, visited)) return true;
            }
            //up
            if (y > 0 && maze[y-1][x] != 1) {
                int i = y - 1;
                while (i > 0 && maze[i-1][x] != 1) i--;
                if (hasPath(maze, new int[]{i, x}, dest, visited)) return true;
            }
            //down
            if (y < maze.length - 1 && maze[y+1][x] != 1) {
                int i = y + 1;
                while (i < maze.length-1 && maze[i+1][x] != 1) i++;
                if (hasPath(maze, new int[]{i, x}, dest, visited)) return true;
            }
            return false;
        }
    }
    

  • 0
    X

    Similar idea:
    C++:https://discuss.leetcode.com/topic/104765/beats-99-27-25ms-straightforward-solution-dfs-without-helper

    class Solution {
    public:
        bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
            if (start == destination) return true;
            int r = start[0], c = start[1];
            maze[r][c] = -1;
            int i = r, m = maze.size(), n = maze.front().size();
    
            for (; i > 0 && maze[i - 1][c] != 1; --i); //up
            vector<int> next { i, c };
            if (i != r && maze[i][c] != -1 && hasPath(maze, next, destination)) return true;
    
            for (i = r; i < m - 1 && maze[i + 1][c] != 1; ++i); //down
            next[0] = i;
            if (i != r && maze[i][c] != -1 && hasPath(maze, next, destination)) return true;
    
            for (i = c; i > 0 && maze[r][i - 1] != 1; --i); //left
            next[0] = r; next[1] = i;
            if (i != c && maze[r][i] != -1 && hasPath(maze, next, destination)) return true;
    
            for (i = c; i < n - 1 && maze[r][i + 1] != 1; ++i); //right
            next[1] = i;
            if (i != c && maze[r][i] != -1 && hasPath(maze, next, destination)) return true;
    
            return false;
        }
    };
    

Log in to reply
 

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