1 Set + 1 Queue = Simple BFS (Java)


  • 0

    Use queue to implement BFS search.
    Use hashset to detect the positions that have been visited before.
    Note 1: can't directly add an array to the hashset to detect repeated positions.
    Note 2: a similar idea can resolve Maze II as well.
    https://discuss.leetcode.com/topic/77621/1-map-1-queue-simple-bfs-java

        public boolean hasPath(int[][] maze, int[] start, int[] destination) {
            Queue<int[]> q = new LinkedList<>();
            Set<String> set = new HashSet<>(); 
            q.offer(start); 
            set.add(start[0] + " " + start[1]); 
            char[] dirs = {'U', 'R', 'D', 'L'};  // explore 4 directions
            while (!q.isEmpty()) {
                int[] cur = q.poll(); 
                for (char dir : dirs) {
                    int[] next = getStop(maze, cur, dir); // get coordinates for the next stop position
                    if (Arrays.equals(next, destination)) return true; 
                    if (!set.contains(next[0] + " " + next[1])) { 
                        set.add(next[0]+ " " +next[1]);  
                        q.offer(next); 
                    }
                }
            }
            return false; 
        }
        
        public int[] getStop (int[][] maze, int[] cur, char dir) {
            int row = cur[0], col = cur[1];
            int m = maze.length, n = maze[0].length;
            switch (dir) {
                case 'U' : while (row != 0 && maze[row - 1][col] != 1) row--; break; 
                case 'R' : while (col != n - 1 && maze[row][col + 1] != 1) col++; break; 
                case 'D' : while (row != m - 1 && maze[row + 1][col] != 1) row++; break; 
                case 'L' : while (col != 0 && maze[row][col - 1] != 1) col--; break;
                default: break; 
            }
            return new int[]{row, col}; 
        }

Log in to reply
 

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