# BFS

#### [841. Keys and Rooms](https://leetcode.com/problems/keys-and-rooms/)

```java
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        if (rooms == null || rooms.size() == 0) {
            return true;
        }
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        visited.add(0);
        while (!q.isEmpty()) {
            int curt = q.poll();
            for (int next : rooms.get(curt)) {
                if (!visited.contains(next)) {
                    q.offer(next);
                    visited.add(next);
                }
            }
        }
        return visited.size() == rooms.size();
    }
```

#### [1091. Shortest Path in Binary Matrix](https://leetcode.com/problems/shortest-path-in-binary-matrix/)

```java
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] != 0 || grid[n - 1][n - 1] != 0) return -1;
        if (grid.length == 1 && grid[0][0] == 0) return 1;
        boolean[][] visited = new boolean[n][n];
        visited[0][0] = true;
        int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0},{1,1}, {-1,-1}, {1,-1}, {-1,1}};
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0, 0});
        int step = 1;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] curt = q.poll();
                for (int[] d : dir) {
                    int nx = curt[0] + d[0];
                    int ny = curt[1] + d[1];
                    if (inbound(grid, nx, ny) && !visited[nx][ny] && grid[nx][ny] == 0) {
                        if (nx == n - 1 && ny == n - 1) return step + 1;
                        visited[nx][ny] = true;
                        q.offer(new int[]{nx, ny});
                    }
                }
            }
            step++;
        }
        return -1;
    }
    
    private boolean inbound(int[][] m, int x, int y) {
        return x >= 0 && y >= 0 && x < m.length && y < m[0].length;
    }
```

#### [994. Rotting Oranges](https://leetcode.com/problems/rotting-oranges/)

Count the number of oranges and rotten oranges. Starting with all rotten oranges in the queue, traverse in **level order** to fill all good oranges. Return the number of levels if the all oranges are rotten (check count).&#x20;

{% tabs %}
{% tab title="Java" %}

```java
int[][] dirs = new int[][]{{0,1}, {1,0}, {0,-1}, {-1,0}};
public int orangesRotting(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    Queue<int[]> q = new LinkedList<>();
    int count = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 2) q.offer(new int[]{i, j});
            else if (grid[i][j] == 1) count++;
        }
    }
    if (count == 0) return 0;
    int step = 0;
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            int[] curt = q.poll();
            for (int[] d : dirs) {
                int nx = curt[0] + d[0];
                int ny = curt[1] + d[1];
                if (nx >= 0 
                    && nx < m 
                    && ny >= 0 
                    && ny < n 
                    && grid[nx][ny] == 1) {
                    grid[nx][ny] = 2;
                    count--;
                    q.offer(new int[]{nx, ny});
                }
            }
        }
        step++;
    }
    return count == 0 ? step - 1 : -1;
}
```

{% endtab %}

{% tab title="Python" %}

```python
    directions = [[0,1],[1,0],[-1,0], [0,-1]]
    def orangesRotting(self, grid: List[List[int]]) -> int:
        queue = []
        orange = 0
        for x in range(0, len(grid)):
            for y in range(0, len(grid[0])):
                if grid[x][y] == 2:
                    queue.append([x, y])
                if grid[x][y] == 1:
                    orange += 1
        if orange == 0:
            return 0
        level = 0
        while queue:
            size = len(queue)
            for k in range(0, size):
                curtx, curty = queue.pop(0)
                if grid[curtx][curty] == 1:
                    grid[curtx][curty] = 2
                    orange -= 1
                    if orange == 0:
                        return level
                for d in self.directions:
                    nx = curtx + d[0]
                    ny = curty + d[1]
                    if self.inbound(grid, nx, ny) and grid[nx][ny] == 1:
                        queue.append([nx, ny])
            level += 1
        if orange == 0:
            return level
        return -1
        
    def inbound(self, grid, x, y) :
        return x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0]) 
```

{% endtab %}
{% endtabs %}

#### [Highest Peak](https://leetcode.com/discuss/interview-question/915485/Google-or-Onsite-or-Highest-Peak)

Given a 2D boolean array where `true` represents water and `false` represents land, generate a grid with highest possible peak. Rules are:

1. the height of any water cell is 0.
2. the height of any land cell **cannot differ for more than one** from any of the neighboring (sharing one edge) cells.

![](/files/-MLnd9gDGigw1ujyxtYo)

> Add all "T" nodes into a BFS queue and trigger a BFS from all those nodes. Also, maintain the distance used to reach each node alongside. Once the BFS visits all the nodes, return the distance to reach every node as the answer.
>
> For the followup:- From all the nodes that have reached max peak height, trigger another BFS that goes from max peak height node to other nodes decrementing the distance. This would lead to more nodes having a height of 0

#### [1162. As Far from Land as Possible](https://leetcode.com/problems/as-far-from-land-as-possible/)

```java
    int[][] directions = new int[][]{{0,1}, {1,0}, {0,-1}, {-1,0}};
    public int maxDistance(int[][] grid) {
        if(grid == null || grid.length == 0 || grid[0].length == 0) return -1;
        int m = grid.length, n = grid[0].length;
        int[][] dist = new int[m][n];
        Queue<int[]> q = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        int count0 = 0, count1 = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    q.offer(new int[]{i, j});
                    visited.add(i * n + j);
                    count1++;
                } else {
                    count0++;
                }
            }
        }
        int res = -1;
        if (count0 == 0 || count1 == 0) return res;
        int level = -1;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] curt = q.poll();
                for (int[] d : directions) {
                    int nx = curt[0] + d[0];
                    int ny = curt[1] + d[1];
                    if (inbound(grid, nx, ny) 
                        && !visited.contains(nx * n + ny) && grid[nx][ny] == 0) {
                            q.offer(new int[]{nx, ny});
                            visited.add(nx * n + ny);
                    }
                }
            }
            level++;
        }
        return level;
    }
    
    private boolean inbound(int[][] matrix, int x, int y) {
        return x >= 0 && y >= 0 && x < matrix.length && y < matrix[0].length;
    }
```

#### [286. Walls and Gates](https://leetcode.com/problems/walls-and-gates/)

```python
    directions = [[0,1],[1,0],[-1,0], [0,-1]]
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        queue = []
        for x in range(0, len(rooms)):
            for y in range(0, len(rooms[0])):
                if (rooms[x][y] == 0):
                    queue.append([x, y])
        level = 0
        while queue:
            size = len(queue)
            for k in range(0, size):
                curtx, curty = queue.pop(0)
                if rooms[curtx][curty] == 2147483647:
                    rooms[curtx][curty] = level
                for d in self.directions:
                    nx = curtx + d[0]
                    ny = curty + d[1]
                    if self.inbound(rooms, nx, ny) and rooms[nx][ny] == 2147483647:
                        queue.append([nx, ny])
            level += 1
        return
    
    def inbound(self, grid, x, y) :
        return x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0]) 
```

#### [130. Surrounded Regions](https://leetcode.com/problems/surrounded-regions/submissions/)

```python
    directions = [[0,1],[1,0],[-1,0], [0,-1]]
    def solve(self, board: List[List[str]]) -> None:
        if not board or len(board) == 0 or len(board[0]) == 0:
            return
        m = len(board)
        n = len(board[0])
        queue = []
        for i in range(0, m):
            if board[i][0] == "O":
                queue.append([i, 0])
            if board[i][n - 1] == "O":
                queue.append([i, n - 1])
        for j in range(0, n):
            if board[0][j] == "O":
                queue.append([0, j])
            if board[m - 1][j] == "O":
                queue.append([m - 1, j])
        while queue:
            x, y = queue.pop(0)
            board[x][y] = "B"  
            for d in self.directions:  ## x= 3,y=1
                nx = x + d[0]
                ny = y + d[1]
                if self.inbound(board, nx, ny) and board[nx][ny] == "O":
                    queue.append([nx, ny])
        
        for i in range(0, m):
            for j in range(0, n):
                if board[i][j] == "O":
                    board[i][j] = "X"
                if board[i][j] == "B":
                    board[i][j] = "O"
        
    
    def inbound(self, grid, x, y) :
        return x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0]) 
```

#### [814. Shortest Path in Undirected Graph](https://www.lintcode.com/problem/shortest-path-in-undirected-graph/description)

![](/files/-MDRs7wKoBnuL_h4vxwC)

```java
public int shortestPath(List<UndirectedGraphNode> graph, UndirectedGraphNode A, UndirectedGraphNode B) {
        // Write your code here
		Queue<UndirectedGraphNode> q = new LinkedList<>();
		Set<UndirectedGraphNode> visited = new HashSet<>();
		q.offer(A);
		visited.add(A);
		int level = 0;
		while (!q.isEmpty()) {
		    level++;
		    int size = q.size();
		    for (int i = 0; i < size; i++) {
		        UndirectedGraphNode curt = q.poll();
		        for (UndirectedGraphNode next : curt.neighbors) {
		            if (next == B) {
		                return level;
		            }
		            if (visited.contains(next)) {
		                continue;
		            }
		            visited.add(next);
		            q.offer(next);
		        }
		    }
		}
		return -1;
}
```

#### [1236. Web Crawler](https://leetcode.com/problems/web-crawler/)

{% tabs %}
{% tab title="Python" %}

```python
    def crawl(self, startUrl: str, htmlParser: 'HtmlParser') -> List[str]:
        visit = set()
        queue = []
        queue.append(startUrl)
        visit.add(startUrl)
        host = startUrl.split("/")[2]
        res = []
        while queue:
            curt = queue.pop(0)
            res.append(curt)
            for next in htmlParser.getUrls(curt):
                if next not in visit and host in next:
                    queue.append(next)
                    visit.add(next)
        return res
```

{% endtab %}

{% tab title="Java" %}

```java
    public List<String> crawl(String startUrl, HtmlParser htmlParser) {
        Set<String> visited = new HashSet<>();
        String hostname = startUrl.split("/")[2];
        Queue<String> q = new LinkedList<>();
        q.offer(startUrl);
        while (!q.isEmpty()) {
            String curt = q.poll();
            visited.add(curt);
            for (String next : htmlParser.getUrls(curt)) {
                if (next.indexOf(hostname) != -1 && !visited.contains(next)) {
                    q.offer(next);
                }
            }
        }
        return new ArrayList<>(visited);
    }
```

{% endtab %}
{% endtabs %}

#### [417. Pacific Atlantic Water Flow](https://leetcode.com/problems/pacific-atlantic-water-flow/)

```java
    int[][] directions = new int[][]{{0,1}, {1,0}, {0,-1}, {-1,0}};
    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return new ArrayList<>();
        int m = matrix.length, n = matrix[0].length;
        boolean[][] pacific = new boolean[m][n];
        boolean[][] atlantic = new boolean[m][n];
        List<List<Integer>> result = new ArrayList<>();
        Queue<int[]> q_P = new LinkedList<>();
        Queue<int[]> q_A = new LinkedList<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (i == 0 || j == 0) {
                    q_P.offer(new int[]{i, j});
                    pacific[i][j] = true;
                }
                if (i == m - 1 || j == n - 1) {
                    q_A.offer(new int[]{i, j});
                    atlantic[i][j] = true;
                }
            }
        }
        BFS(matrix, q_P, pacific);
        BFS(matrix, q_A, atlantic);
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    result.add(Arrays.asList(new Integer[]{i, j}));    
                }
            }
        }
        return result;
    }
    
    private void BFS(int[][] matrix, Queue<int[]> q, boolean[][] visited) {
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] curt = q.poll();
                int x = curt[0], y = curt[1];
                for (int[] d : directions) {
                    int nx = x + d[0];
                    int ny = y + d[1];
                    if (inbound(matrix, nx, ny)
                        && matrix[nx][ny] >= matrix[x][y]
                        && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        q.offer(new int[]{nx, ny});
                    }
                }
            }
        }
    }
    
    private boolean inbound(int[][] matrix, int x, int y) {
        return x >= 0 && y >= 0 && x < matrix.length && y < matrix[0].length;
    }
```

#### [815. Bus Routes](https://leetcode.com/problems/bus-routes/)

Build graph by using stop to next available stops. Level order BFS to find the next stops, return step/level when reach stop T. (*This answer will return TLE when there are too many stops*)

```java
   public int numBusesToDestination(int[][] routes, int S, int T) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] route : routes) {
            for (int i = 0; i < route.length; i++) {
                for (int j = 0; j < route.length; j++) {
                    if (i == j) continue;
                    map.putIfAbsent(route[i], new HashSet<>());
                    map.putIfAbsent(route[j], new HashSet<>());
                    map.get(route[i]).add(route[j]);
                    map.get(route[j]).add(route[i]);
                }
            }
        }
        Queue<Integer> q = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        q.offer(S);
        int level = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int curt = q.poll();
                if (curt == T) return level;
                if (map.get(curt) == null) continue;
                for (int next : map.get(curt)) {
                    if (next == T) return level + 1;
                    if (visited.contains(next)) continue;
                    visited.add(next);
                    q.offer(next);
                }
            }
            level++;
        }
        return -1;
    }
```

One modification is to check **duplicate on bus route, instead of bus stops**. That will eliminate lots of path since all stops on traveled path are redundant.&#x20;

```java
    public int numBusesToDestination(int[][] routes, int S, int T) {
        if (S == T) return 0;
        Map<Integer, Set<Integer>> map = new HashMap<>(); // stop : buses
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < routes.length; i++) {
            for (int n : routes[i]) {
                map.putIfAbsent(n, new HashSet<>());
                map.get(n).add(i);
            }
        }
        if (!map.containsKey(S)) return -1;
        Set<Integer> visited = new HashSet<>(); 
        int count = 0;
        q.offer(S);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int k = 0; k < size; k++) {
                int curt = q.poll();
                if (curt == T) return count + 1;
                for (int r : map.get(curt)) {
                    if (visited.contains(r)) continue;
                    visited.add(r);
                    for (int next : routes[r]) {
                        if (next == T) return count + 1;
                        q.offer(next);
                    }
                }
            }
            count++;
        }
        return -1;
    }
```

*N is number of stops, T is the stops \* edges:  T: O(n^2)*

#### [490. The Maze](https://leetcode.com/problems/the-maze/)

Find the next node by extending the directions, until reach boundary or wall. Use `boolean[][] visited` to record all visited nodes.

```java
    int[][] dirs = {{1,0} , {0,1}, {-1,0}, {0,-1}};
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        boolean[][] visited = new boolean[maze.length][maze[0].length];
        Queue<int[]> q = new LinkedList<>();
        q.offer(start);
        visited[start[0]][start[1]] = true;
        while (!q.isEmpty()) {
            int[] curt = q.poll();
            if (curt[0] == destination[0] && curt[1] == destination[1]) {
                return true;
            }
            for (int[] dir : dirs) {
                int x = curt[0];
                int y = curt[1];
                while (inbound(maze, x + dir[0], y + dir[1]) 
                       && maze[x + dir[0]][y + dir[1]] != 1) {
                    x += dir[0];
                    y += dir[1];
                }
                if (x == destination[0] && y == destination[1]) {
                    return true;
                }
                if (!visited[x][y]) {
                    visited[x][y] = true;
                    q.offer(new int[]{x, y});
                }
            }
        }
        return false;
    }
    
    private boolean inbound(int[][] maze, int x, int y) {
        return x >= 0 && y >= 0 && x < maze.length && y < maze[0].length;
    }
```

#### [505. The Maze II](https://leetcode.com/problems/the-maze-ii/)

The BFS solution requires to store all path to destination. Use a `dist` matrix to store the minimum distance between each grid and start point. Replace the distance when new calculated steps is less than the earlier calculations. Output result as all distances are calculated.&#x20;

```java
int[][] direction = new int[][]{{1,0}, {0,1}, {-1,0}, {0,-1}};
public int shortestDistance(int[][] maze, int[] start, int[] destination) {
    if (start == null || destination == null || maze == null || maze.length == 0 || maze[0].length == 0) {
        return -1;
    }
    int m = maze.length, n = maze[0].length;
    int[][] dist = new int[m][n];
    for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);

    Queue<int[]> q = new LinkedList<>();
    q.offer(start);
    dist[start[0]][start[1]] = 0;
    while (!q.isEmpty()) {
        int[] curt = q.poll();
        for (int[] d : direction) {
            int nx = curt[0];
            int ny = curt[1];
            int step = 0;
            while (inbound(maze, nx + d[0], ny + d[1]) && maze[nx + d[0]][ny + d[1]] == 0) {
                nx += d[0];
                ny += d[1];
                step++;
            }
            if (dist[nx][ny] > dist[curt[0]][curt[1]] + step) {
                dist[nx][ny] = dist[curt[0]][curt[1]] + step;
                q.offer(new int[]{nx, ny});
            }
        }
    }
    return dist[destination[0]][destination[1]] == Integer.MAX_VALUE ? -1 
                                : dist[destination[0]][destination[1]];
}

private boolean inbound(int[][] grid, int x, int y) {
    return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
}
```

[Solution: Dijkstra](/decode-leetcode/graph/dijkstra.md#505-the-maze-ii)

#### [611. Knight Shortest Path \[LintCode\]](https://www.lintcode.com/problem/knight-shortest-path/)

Given a knight in a chessboard (a binary matrix with 0as empty a 1as barrier) with a source position, find the shortest path to a destination position, return the length of the route.

Return -1 if knight can not reached.

Notice

* Source and destination must be empty.
* Knight can not enter the barrier.

![](/files/-MCr6nhTrfnlI1t7eDev)

```java
    int[][] directions = {{1, 2}, {2, 1}, {-1, 2}, {-2, 1},
            {1, -2}, {2, -1}, {-1, -2}, {-2, -1}};
    public int knightshortestpath(int[][] grid, int[] start, int[] destination) {
        if(grid == null || grid.length == 0 ||
                grid[0].length == 0 || start == null || destination == null){
            return -1;
        }
        if (start[0] == destination[0] && start[1] == destination[1]) {
            return 0;
        }
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(start);
        grid[start[0]][start[1]] = 2;
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] curt = queue.poll();
                for (int[] d : directions) {
                    int nx = curt[0] + d[0];
                    int ny = curt[1] + d[1];
                    if (nx == destination[0] && ny == destination[1]) {
                        return level + 1;
                    }
                    if (inbound(grid, nx, ny) && grid[nx][ny] == 0) {
                        grid[nx][ny] = 2;
                        queue.offer(new int[]{nx, ny});
                    }
                }
            }
            level++;
        }
        return -1;
    }

    private boolean inbound(int[][] grid, int x, int y) {
        return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
    }
```

#### [542. 01 Matrix](https://leetcode.com/problems/01-matrix/)

Fill the result matrix with Integer.MAX\_VALUE to detect if the node has been visited. Starting from 0 grids, use BFS to detect if the next distance from 0 is larger than expected, if so, correct it to the right value. Offer that next node to the queue.

*T: O(m \* n) S: O(m \* n)*

```java
    int[][] dirs = {{1,0} , {0,1}, {-1,0}, {0,-1}};
    public int[][] updateMatrix(int[][] matrix) {
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    q.offer(new int[]{i, j});
                } else {
                    matrix[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        while (!q.isEmpty()) {
            int[] curt = q.poll();
            for (int[] d : dirs) {
                int nx = curt[0] + d[0];
                int ny = curt[1] + d[1];
                if (inbound(matrix, nx, ny) && matrix[nx][ny] > matrix[curt[0]][curt[1]] + 1) {
                    matrix[nx][ny] = matrix[curt[0]][curt[1]] + 1;
                    q.offer(new int[]{nx, ny});
                }
            }
        }
        return matrix;
    }
    
    private boolean inbound(int[][] matrix, int x, int y) {
        return x >= 0 && y >= 0 && x < matrix.length && y < matrix[0].length;
    }
```

#### [127. Word Ladder](https://leetcode.com/problems/word-ladder/)

*T: O(k^2 \* N)    N is number of words and k is the average length of words*

{% tabs %}
{% tab title="Java" %}

```java
    public int ladderLength(String beginWord,
                            String endWord,
                            List<String> wordList) {
        if (beginWord == null || endWord == null 
                || beginWord.isEmpty() || endWord.isEmpty()) {
            return 0;
        }
        if (beginWord.equals(endWord)) return 0;
        Set<String> dict = new HashSet<>();
        dict.addAll(wordList);
        if (!dict.contains(endWord)) return 0;
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        Queue<String> q = new LinkedList<>();
        q.offer(beginWord);
        int level = 1;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String curt = q.poll();
                for (String next : getNexts(curt, dict)) {
                    if (next.equals(endWord)) return level + 1;
                    if (visited.contains(next)) continue;
                    visited.add(next);
                    q.offer(next);
                }
            }
            level++;
        }
        return 0;
    }
    
    private Set<String> getNexts(String s, Set<String> dict) {
        Set<String> result = new HashSet<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char old = chars[i];
            for (char c = 'a'; c <= 'z'; c++) {
                chars[i] = c;
                String next = String.valueOf(chars);
                if (dict.contains(next)) result.add(next);
            }
            chars[i] = old;
        }
        return result;
    }
```

{% endtab %}

{% tab title="Python" %}

```python
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        dic = set(wordList)
        if endWord not in dic:
            return 0
        queue = []
        visit = set()
        queue.append(beginWord)
        visit.add(beginWord)
        level = 1
        while queue:
            size = len(queue)
            for i in range(size):
                curt = queue.pop(0)
                for next in self.getNext(curt, dic, visit):
                    if next == endWord:
                        return level + 1
                    if next in dic and next not in visit:
                        visit.add(next)
                        queue.append(next)
            level += 1
        return 0
    
    def getNext(self, s, dic, visit):
        res = []
        for i in range(len(s)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                new = s[:i] + c + s[i + 1:]
                if new in dic and new not in visit:
                    res.append(new)
        return res
```

{% endtab %}
{% endtabs %}

#### [126. Word Ladder II](https://leetcode.com/problems/word-ladder-ii/)

Use BFS level order traversal to build graph and record distance from start node. DFS to build path.

```java
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Map<String, Integer> dist = new HashMap<>();
        Map<String, Set<String>> graph = new HashMap<>();
        Set<String> dict = new HashSet<>();
        dict.addAll(wordList);
        List<List<String>> res = new ArrayList<>();
        if (!dict.contains(endWord) || beginWord.equals(endWord)) return res;
        bfsBuildGraph(beginWord, endWord, dict, dist, graph);
        List<String> list = new ArrayList<>();
        list.add(beginWord);
        dfs(beginWord, endWord, list, res, dist, graph);
        return res;
    }

    private void dfs(String curt,
                     String target,
                     List<String> list,
                     List<List<String>> result,
                     Map<String, Integer> dist,
                     Map<String, Set<String>> graph) {
        if (curt.equals(target)) {
            result.add(new ArrayList<>(list));
            return;
        }
        if (graph.get(curt) == null) return;
        for (String next : graph.get(curt)) {
            if (dist.get(next) == dist.get(curt) + 1) {
                list.add(next);
                dfs(next, target, list, result, dist, graph);
                list.remove(list.size() - 1);
            }
        }
    }

    private void bfsBuildGraph(String beginWord,
                              String endWord,
                              Set<String> dict,
                               Map<String, Integer> dist,
                               Map<String, Set<String>> graph) {
        Queue<String> q = new LinkedList<>();
        q.offer(beginWord);
        dist.put(beginWord, 0);
        boolean foundEnd = false;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String curt = q.poll();
                int d = dist.get(curt);
                graph.putIfAbsent(curt, new HashSet<>());
                for (String next : getNexts(curt, dict)) {
                    graph.get(curt).add(next);
                    if (next.equals(endWord)) foundEnd = true;
                    if (dist.containsKey(next)) continue;
                    dist.put(next, d + 1);
                    q.offer(next);
                }
            }
            if (foundEnd) break;
        }
    }
    
    private Set<String> getNexts(String s, Set<String> dict) {
        Set<String> result = new HashSet<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char old = chars[i];
            for (char c = 'a'; c <= 'z'; c++) {
                chars[i] = c;
                String next = String.valueOf(chars);
                if (dict.contains(next)) result.add(next);
            }
            chars[i] = old;
        }
        return result;
    }
```

#### [133. Clone Graph](https://leetcode.com/problems/clone-graph/)

Use a map to store the relationship `key: current node value: corresponding new node`. Traverse the graph with a curt node and add corresponding neighbors to the `neighbors` list.

T: O(n)

{% tabs %}
{% tab title="Java" %}

```java
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        Map<Node, Node> map = new HashMap<>();
        Queue<Node> q = new LinkedList<>();
        map.put(node, new Node(node.val, new ArrayList<>()));
        q.offer(node);
        while (!q.isEmpty()) {
            Node curt = q.poll();
            for (Node next : curt.neighbors) {
                if (!map.containsKey(next)) {
                    map.put(next, new Node(next.val, new ArrayList<>()));
                    q.offer(next);
                }
                map.get(curt).neighbors.add(map.get(next));
            }
        }
        return map.get(node);
    }
```

{% endtab %}

{% tab title="Python" %}

```python
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None
        dic = {}
        visited = set()
        queue = []
        queue.append(node)
        visited.add(node)
        dic[node] = Node(node.val)
        while queue:
            curt = queue.pop(0)
            for next in curt.neighbors:
                if next not in visited:
                    dic[next] = Node(next.val)
                    queue.append(next)
                    visited.add(next)
                dic[curt].neighbors.append(dic[next])
        return dic[node]
```

{% endtab %}
{% endtabs %}

DFS [link](/decode-leetcode/dfs.md#133-clone-graph)

#### [261. Graph Valid Tree](https://leetcode.com/problems/graph-valid-tree/)

{% tabs %}
{% tab title="Java" %}

```java
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) {
            return false;
        }
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            map.putIfAbsent(u, new HashSet<>());
            map.putIfAbsent(v, new HashSet<>());
            map.get(u).add(v);
            map.get(v).add(u);
        }
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        visited.add(0);
        while (!q.isEmpty()) {
            int curt = q.poll();
            if (map.get(curt) == null) continue;
            for (int next : map.get(curt)) {
                map.get(next).remove(curt);
                if (visited.contains(next)) {
                    return false;
                }
                visited.add(next);
                q.offer(next);
            }
        }
        return visited.size() == n;
    }
```

{% endtab %}

{% tab title="Python" %}

```python
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if n != len(edges) + 1:
            return False
        graph = [[] for i in range(n)]
        indegree = [0] * n
        for v, u in edges:
            graph[u].append(v)
            graph[v].append(u)
            
        queue = []
        visited = set()
        queue.append(0)
        visited.add(0)
        while queue:
            curt = queue.pop(0)
            for next in graph[curt]:
                if next in visited:
                    return False
                graph[next].remove(curt)
                visited.add(next)
                queue.append(next)
        return len(visited) == n
```

{% endtab %}
{% endtabs %}

#### [909. Snakes and Ladders](https://leetcode.com/problems/snakes-and-ladders/)

Convert index to board by using:

* **int row = n - (next - 1) / n - 1**
* **int col = (n - row) % 2 != 0 ? (next - 1) % n : n - (next - 1) % n - 1**

```java
    public int snakesAndLadders(int[][] board) {
        if (board == null || board.length == 0) return 0;
        int n = board.length;
        Queue<Integer> q = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        q.offer(1);
        visited.add(1);
        int step = 0, min = Integer.MAX_VALUE;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int curt = q.poll();
                if (curt == n * n) min = Math.min(min, step);
                for (int k = 1; k <= 6; k++) {
                    int next = curt + k;
                    if (next > n * n) break;
                    if (visited.contains(next)) continue;
                    visited.add(next);
                    int row = n - (next - 1) / n - 1;
                    int col = (n - row) % 2 != 0 ? (next - 1) % n
                                                 : n - (next - 1) % n - 1;
                    if (board[row][col] == curt) continue;
                    if (board[row][col] == -1) {
                        q.offer(next);
                    } else {
                        q.offer(board[row][col]);
                    }
                }
            }
            step++;
        } 
        return min == Integer.MAX_VALUE ? -1 : min;
    }
```

#### [752. Open the Lock](https://leetcode.com/problems/open-the-lock/)

Similar as 127. Word Ladder.&#x20;

{% tabs %}
{% tab title="Java" %}

```java
    public int openLock(String[] deadends, String target) {
        Set<String> deads = new HashSet<>();
        for (String d : deadends) {
            if (d.equals("0000")) {
                return -1;
            }
            deads.add(d);
        }
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer("0000");
        visited.add("0000");
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String curt = queue.poll();
                if (curt.equals(target)) return level;
                for (String next : getNexts(curt, deads, visited)) {
                    if (visited.contains(next)) {
                        continue;
                    }
                    visited.add(next);
                    queue.offer(next);
                }
            }
            level++;
        }
        return -1;
    }

   private Set<String> getNexts(String curt, Set<String> deads, Set<String> visited) {
     Set<String> nextCurs = new HashSet<>();
        char[] chars = curt.toCharArray();
        for (int i = 0; i < 4; i++) {
            char origin = chars[i];
            chars[i] = (char)((origin - '0' + 1) % 10 + '0');
            String next = new String(chars);

            if (!deads.contains(next) && !visited.contains(next)) {
                nextCurs.add(next);
            }
            chars[i] = (char)((origin - '0' - 1 + 10) % 10 + '0');
            next = new String(chars);

            if (!deads.contains(next) && !visited.contains(next)) {
                nextCurs.add(next);
            }
            chars[i] = origin;
        }
        return nextCurs;
    }
```

{% endtab %}

{% tab title="Python" %}

```python
    def openLock(self, deadends: List[str], target: str) -> int:
        start = "0000"
        dead = set(deadends)
        if start in dead:
            return -1
        visited = set()
        queue = []
        queue.append(start)
        visited.add(start)
        level = 0
        while queue:
            level += 1
            size = len(queue)
            for i in range(size):
                curt = queue.pop(0)
                for next in self.getnexts(curt):
                    if target == next:
                        return level
                    if next not in visited and next not in dead:
                        queue.append(next)
                        visited.add(next)
        return -1
        
    
    def getnexts(self, s):
        for i in range(4):
            yield s[:i] + str((int(s[i]) + 1) % 10) + s[i+1:]
            yield s[:i] + str((int(s[i]) - 1) % 10) + s[i+1:]
```

{% endtab %}
{% endtabs %}

#### [1088. Confusing Number II](https://leetcode.com/problems/confusing-number-ii/)

Check on `curt` get TLE, however check both on `curt` and `next` should work.

{% tabs %}
{% tab title="Java" %}

```java
    Map<Integer, Integer> map;
    public int confusingNumberII(int N) {
        map = new HashMap<>();
        map.put(0, 0);
        map.put(1, 1);
        map.put(6, 9);
        map.put(8, 8);
        map.put(9, 6);
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        int count = 0;
        Set<Integer> set = new HashSet<>();
        set.add(0);
        while (!q.isEmpty()) {
            int curt = q.poll();
            for (int d : map.keySet()) {
                int next = curt * 10 + d;
                if (next > N) return count; 
                if (next != 0) {
                    q.offer(next);
                }
                if (isConfusing(next) && !set.contains(next)) {
                    set.add(next);
                    count++;
                }
            }
        }
        return count;
    }
    
    private boolean isConfusing(int n) {
        long rot = 0;
        int tmp = n;
        while (n > 0) {
            rot = rot * 10 + map.get(n % 10);
            n /= 10;
        }
        return rot != tmp;
    }
```

{% endtab %}

{% tab title="Java (Check on curt)" %}

```java
    Map<Integer, Integer> map;
    public int confusingNumberII(int N) {
        map = new HashMap<>();
        map.put(0, 0);
        map.put(1, 1);
        map.put(6, 9);
        map.put(8, 8);
        map.put(9, 6);
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        int count = 0;
        Set<Integer> set = new HashSet<>();
        while (!q.isEmpty()) {
            int curt = q.poll();
            if (curt > N) break; 
            if (isConfusing(curt) && !set.contains(curt)) {
                set.add(curt);
                count++;
            }
            for (int d : map.keySet()) {
                q.offer(curt * 10 + d);
            }
        }
        return count;
    }
    
    private boolean isConfusing(int n) {
        long rot = 0;
        int tmp = n;
        while (n > 0) {
            rot = rot * 10 + map.get(n % 10);
            n /= 10;
        }
        return rot != tmp;
    }
```

{% endtab %}
{% endtabs %}

#### [1129. Shortest Path with Alternating Colors](https://leetcode.com/problems/shortest-path-with-alternating-colors/)

```java
    public int[] shortestAlternatingPaths(int n, int[][] red_edges, int[][] blue_edges) {
        int[][] graph = new int[n][n];
        buildGraph(graph, n, red_edges, blue_edges);
        Queue<int[]> q = new LinkedList<>();
        Set<String> set = new HashSet<>();
        q.offer(new int[]{0, 1});
        q.offer(new int[]{0, -1});
        
        int[] res = new int[n];
        Arrays.fill(res, Integer.MAX_VALUE);
        res[0] = 0;
        
        int level = 0;
        while (!q.isEmpty()) {
            level++;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] curt = q.poll();
                int node = curt[0], color = curt[1];
                for (int k = 0; k < n; k++) {
                    if (graph[node][k] == 0 || graph[node][k] == -color) {
                        if (!set.add(k + " " + (-color))) continue;
                        q.offer(new int[]{k, -color});
                        res[k] = Math.min(res[k], level);
                    }
                }
            }
        }
        for (int i = 1; i < n; i++) {
            if (res[i] == Integer.MAX_VALUE) {
                res[i] = -1;
            }
        }
        return res;
    }
    
    private void buildGraph(int[][] g, int n, int[][] red_edges, int[][] blue_edges) {
        for (int i = 0; i < n; i++) {
            Arrays.fill(g[i], -n);
        }
        for (int[] e : red_edges) {
            g[e[0]][e[1]] = 1;
        }
        for (int[] e : blue_edges) {
            int from = e[0];
            int to = e[1];
            if (g[from][to] == 1) {
                g[from][to] = 0;
            } else {
                g[from][to] = -1;
            }
        }
    }
```

#### [317. Shortest Distance from All Buildings](https://leetcode.com/problems/shortest-distance-from-all-buildings/)

bfs level order traverse starts from all buildings, go through all each empty grids, to calculate the cumulated shortest distance from all buildings. Also count how many houses can reach this spot, when output, detect if this spot can be reached by all starting points.&#x20;

*T: O((mn)^2) .S: O(mn)*&#x20;

```java
    int[][] direction = new int[][]{{1,0}, {0,1}, {-1,0}, {0,-1}};
    public int shortestDistance(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return -1;
        int m = grid.length, n = grid[0].length;
        int[][] dist = new int[m][n], count = new int[m][n];
        int house = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    house++;
                    dist[i][j] = -1;
                    bfs(grid, dist, count, i, j);
                } else if (grid[i][j] == 2) {
                    dist[i][j] = -1;
                }
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][j] != -1 && grid[i][j] == 0 && count[i][j] == house) {
                    min = Math.min(min, dist[i][j]);
                }
            }
        } 
        return min == Integer.MAX_VALUE ? -1 : min;
    }
    
    private void bfs(int[][] grid, int[][] dist, int[][] count, int x, int y) {
        int n = grid[0].length;
        Set<Integer> set = new HashSet<>();
        Queue<int[]> q = new LinkedList<>();
        set.add(x * n + y);
        q.offer(new int[]{x, y});
        int level = 0;
        while (!q.isEmpty()) {
            level++;
            int size = q.size();
            for (int k = 0; k < size; k++) {
                int[] curt = q.poll();
                for (int[] d : direction) {
                    int nx = curt[0] + d[0];
                    int ny = curt[1] + d[1];
                    if (inbound(nx, ny, grid) 
                        && !set.contains(nx * n + ny) 
                        && grid[nx][ny] != 1 
                        && grid[nx][ny] != 2) {
                        count[nx][ny]++;
                        dist[nx][ny] += level;
                        set.add(nx * n + ny);
                        q.offer(new int[]{nx, ny});
                    }
                }
            }
        }
    }
    
    private boolean inbound(int x, int y, int[][] grid) {
        return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
    }
```

#### [864. Shortest Path to Get All Keys](https://leetcode.com/problems/shortest-path-to-get-all-keys/)

```java
    int x = -1, y = -1;
    int max = -1;
    int[][] direction = new int[][]{{1,0}, {0,1}, {-1,0}, {0,-1}};
    public int shortestPathAllKeys(String[] grid) {
        int m = grid.length, n = grid[0].length();
        char[][] g = new char[m][n];
        for (int i = 0; i < grid.length; i++) {
            g[i] = grid[i].toCharArray();
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == '@') {
                    x = i;
                    y = j;
                } else if (g[i][j] >= 'a' && g[i][j] <= 'z') {
                    max = Math.max(g[i][j] - 'a' + 1, max);
                }
            }
        }
        Queue<Node> q = new LinkedList<>();
        Set<String> set = new HashSet<>();
        set.add(0 + " " + x + " " + y);
        q.offer(new Node(x, y, 0));
        int level = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Node curt = q.poll();
                if (curt.keys == Math.pow(2, max) - 1) {
                    return level;
                }
                for (int[] d : direction) {
                    int nx = curt.x + d[0];
                    int ny = curt.y + d[1];
                    int keys = curt.keys;
                    if (inbound(g, nx, ny)) {
                        if (g[nx][ny] == '#') continue;
                        if (g[nx][ny] >= 'a' && g[nx][ny] <= 'z') {
                            keys |= 1 << g[nx][ny] - 'a';
                        }
                        if (g[nx][ny] >= 'A' && g[nx][ny] <= 'Z' && ((keys >> (g[nx][ny] - 'A')) & 1) == 0) {
                            continue;    
                        }
                        if (!set.contains(keys + " " + nx + " " + ny)) {
                            set.add(keys + " " + nx + " " + ny);
                            q.offer(new Node(nx, ny, keys));
                        }
                    }
                }
            }
            level++;
        }
        return -1;
    }
    
    class Node {
        int x, y, keys;
        public Node(int x, int y, int keys) {
            this.x = x;
            this.y = y;
            this.keys = keys;
        }
    }
    
    private boolean inbound(char[][] grid, int x, int y) {
        return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
    }
```

#### [773. Sliding Puzzle](https://leetcode.com/problems/sliding-puzzle/)

{% tabs %}
{% tab title="Java" %}

```java
    public int slidingPuzzle(int[][] board) {
        StringBuilder start = new StringBuilder();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) start.append(board[i][j]);
        }
        int[][] nexts = {{1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {2,4}};
        String target = "123450";
        Queue<String> q = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        visited.add(start.toString());
        q.offer(start.toString());
        int step = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String curt = q.poll();
                if (curt.equals(target)) return step;
                int zero = curt.indexOf('0');
                if (zero == -1) return -1;
                for (int next : nexts[zero]) {
                    StringBuilder sb = new StringBuilder(curt);
                    char temp = sb.charAt(next);
                    sb.setCharAt(zero, temp);
                    sb.setCharAt(next, '0');
                    String n = sb.toString();
                    if (n.equals(target)) return step + 1;
                    if (visited.contains(n)) continue;
                    q.offer(n);
                    visited.add(n);
                }
            }
            step++;
        }
        return -1;
    }
```

{% endtab %}

{% tab title="Java 2" %}

```java
    int[][] move = {{1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {2,4}};
    public int slidingPuzzle(int[][] board) {
        String target = "123450";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                sb.append(board[i][j]);
            }
        }
        String start = sb.toString();
        if (start.equals(target)) {
            return 0;
        }
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(start);
        visited.add(start);
        int level = 0;
        while (!queue.isEmpty()) {
            level++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String curt = queue.poll();
                for (String next : getNext(curt)) {
                    if (next.equals(target)) {
                        return level;
                    }
                    if (!visited.contains(next)) {
                        queue.offer(next);
                        visited.add(next);
                    }
                }
            }
        }
        return -1;
    }
    
    private Set<String> getNext(String s) {
        Set<String> set = new HashSet<>();
        StringBuilder sb = new StringBuilder(s);
        int u = s.indexOf("0");
        char uchar = sb.charAt(u);
        for (int v : move[u]) {
            char vchar = sb.charAt(v);
            sb.setCharAt(v, uchar);
            sb.setCharAt(u, vchar);
            set.add(sb.toString());
            System.out.println(sb.toString());
            sb = new StringBuilder(s);
        }
        return set;
    }
```

{% endtab %}
{% endtabs %}

#### [847. Shortest Path Visiting All Nodes](https://leetcode.com/problems/shortest-path-visiting-all-nodes/)

#### [1293. Shortest Path in a Grid with Obstacles Elimination](https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/)

{% tabs %}
{% tab title="Java" %}

```java
public int shortestPath(int[][] grid, int k) {
    int step = 0;
    int m = grid.length;
    int n = grid[0].length;
    int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int[][] seen = new int[m][n]; // min obstacles elimination from (0,0) to (x, y)
    for (int i = 0; i < m; i++) {
        Arrays.fill(seen[i], Integer.MAX_VALUE);
    }
    Queue<int[]> q = new LinkedList<>();
    q.offer(new int[]{0, 0, 0});
    seen[0][0] = 0;
    while (!q.isEmpty()) {
        int size = q.size();
        while (size-- > 0) {
            int[] cur = q.poll();
            if (cur[0] == m - 1 && cur[1] == n - 1) {
                return step;
            }
            for (int[] dir : DIRS) {
                int x = dir[0] + cur[0];
                int y = dir[1] + cur[1];
                if (x < 0 || x >= m || y < 0 || y >= n) {
                    continue;
                }
                int o = grid[x][y] + cur[2];
                if (o >= seen[x][y] || o > k) {
                    continue;
                }
                seen[x][y] = o;
                q.offer(new int[]{x, y, o});
            }
        }
        ++step;
    }
    return -1;  
}
```

{% endtab %}
{% endtabs %}

#### [675. Cut Off Trees for Golf Event](https://leetcode.com/problems/cut-off-trees-for-golf-event/)

{% tabs %}
{% tab title="Java" %}

```java
    int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public int cutOffTree(List<List<Integer>> forest) {
        if (forest == null || forest.size() == 0 || forest.get(0).size() == 0) {
            return -1;
        }
        List<int[]> treeHeights = getAllTreeHights(forest);
        Collections.sort(treeHeights, (a, b) -> (a[2] - b[2]));
        int i = 0;
        int[] pre = new int[]{0, 0};
        int step = 0;
        while (i < treeHeights.size()) {
            int[] curt = treeHeights.get(i);
            int s = getMinimumSteps(forest, pre[0], pre[1], curt[0], curt[1]);
            if (s == -1) return -1;
            step += s;
            pre[0] = curt[0];
            pre[1] = curt[1];
            forest.get(pre[0]).set(pre[1], 1);
            i++;
        }
        return step;
    }

    private int getMinimumSteps(List<List<Integer>> forest, int curX, int curY, int aimX, int aimY) {
        int n = forest.get(0).size();
        Queue<int[]> q = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        q.offer(new int[]{curX, curY});
        visited.add(curX * n + curY);
        int level = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] curt = q.poll();
                if (curt[0] == aimX && curt[1] == aimY) {
                    return level;
                }
                for (int[] d : directions) {
                    int nx = curt[0] + d[0];
                    int ny = curt[1] + d[1];
                    if (inbound(forest, nx, ny) && !visited.contains(nx * n + ny) && forest.get(nx).get(ny) != 0) {
                        visited.add(nx * n + ny);
                        q.offer(new int[]{nx, ny});
                    }
                }
            }
            level++;
        }
        return -1;
    }

    private List<int[]> getAllTreeHights(List<List<Integer>> forest) {
        List<int[]> treeHeights = new LinkedList<>();
        for (int i = 0; i < forest.size(); i++) {
            for (int j = 0; j < forest.get(0).size(); j++) {
                int[] res = new int[3];
                res[0] = i;
                res[1] = j;
                res[2] = forest.get(i).get(j);
                if (res[2] > 1) {
                    treeHeights.add(res);
                }
            }
        }
        return treeHeights;
    }
    
    private boolean inbound(List<List<Integer>> forest, int x, int y) {
        return x >= 0 && y >= 0 && x < forest.size() && y < forest.get(0).size();
    }
```

{% endtab %}

{% tab title="Python" %}

```python
import collections
class Solution(object):
    def cutOffTree(self, G):
        """
        :type forest: List[List[int]]
        :rtype: int
        """
        if not G or not G[0]: return -1
        m, n = len(G), len(G[0])
        trees = []
        for i in xrange(m):
            for j in xrange(n):
                if G[i][j] > 1:
                    trees.append((G[i][j], i, j))
        trees = sorted(trees)
        count = 0
        cx, cy = 0, 0
        for h, x, y in trees:
            step = self.BFS(G, cx, cy, x, y)
            if step == -1:
                return -1
            else:
                count += step
                G[x][y] = 1
                cx, cy = x, y
        return count

    def BFS(self, G, cx, cy, tx, ty):
        m, n = len(G), len(G[0])
        visited = [[False for j in xrange(n)] for i in xrange(m)]
        Q = collections.deque()
        step = -1
        Q.append((cx, cy))
        while len(Q) > 0:
            size = len(Q)
            step += 1
            for i in xrange(size):
                x, y = Q.popleft()
                visited[x][y] = True
                if x == tx and y == ty:
                    return step
                for nx, ny in [(x + 1, y), (x - 1, y), (x, y-1), (x, y + 1)]:
                    if nx < 0 or nx >= m or ny < 0 or ny >= n or G[nx][ny] == 0 or visited[nx][ny]:
                        continue
                    Q.append((nx, ny))
        return -1
```

{% endtab %}
{% endtabs %}

#### [1345. Jump Game IV](https://leetcode.com/problems/jump-game-iv/)

BFS Level order traversal.

{% tabs %}
{% tab title="Java" %}

```java
public int minJumps(int[] arr) {
    int n = arr.length;
    HashMap<Integer, List<Integer>> indicies = new HashMap<>();
    for (int i = 0; i < n; i++)
        indicies.computeIfAbsent(arr[i], x -> new LinkedList<>()).add(i);
    boolean[] visited = new boolean[n];
    Queue<Integer> q = new LinkedList<>();
    q.offer(0);
    int level = 0;
    visited[0] = true;
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            int index = q.poll();
            if (index == n - 1) {
                return level;
            }
            List<Integer> nexts = indicies.get(arr[index]);
            nexts.add(index + 1);
            nexts.add(index - 1);
            for (int next : nexts) {
                if (next >= 0 && next < n && !visited[next] && next != index) {
                    q.offer(next);
                    visited[next] = true;
                }
            }
            nexts.clear();
        }
        level++;
    }
    return -1;
}
```

{% endtab %}
{% endtabs %}

[2096. Step-By-Step Directions From a Binary Tree Node to Another](https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/)

```java
import java.util.*;

public class Solution {
    private static final String L = "L";
    private static final String R = "R";
    private static final String U = "U";

    private Map<TreeNode, List<DirNode>> map;
    private TreeNode root;
    private int startValue;

    public String getDirections(TreeNode root, int startValue, int destValue) {
        this.map = new HashMap<>();
        this.startValue = startValue;
        this.root = root;

        buildGraph(root);

        TreeNode startNode = findNode(root, startValue);
        if (startNode == null) return "";

        Queue<Pair> queue = new LinkedList<>();
        Set<TreeNode> visited = new HashSet<>();
        queue.offer(new Pair(startNode, ""));
        visited.add(startNode);

        while (!queue.isEmpty()) {
            Pair curr = queue.poll();
            TreeNode node = curr.node;
            String path = curr.path;

            if (node.val == destValue) {
                return path;
            }

            for (DirNode next : map.getOrDefault(node, Collections.emptyList())) {
                if (!visited.contains(next.node)) {
                    visited.add(next.node);
                    queue.offer(new Pair(next.node, path + next.dir));
                }
            }
        }

        return "";  // No path found
    }

    private void buildGraph(TreeNode node) {
        if (node == null) return;

        if (node.left != null) {
            map.computeIfAbsent(node, k -> new ArrayList<>()).add(new DirNode(L, node.left));
            map.computeIfAbsent(node.left, k -> new ArrayList<>()).add(new DirNode(U, node));
            buildGraph(node.left);
        }

        if (node.right != null) {
            map.computeIfAbsent(node, k -> new ArrayList<>()).add(new DirNode(R, node.right));
            map.computeIfAbsent(node.right, k -> new ArrayList<>()).add(new DirNode(U, node));
            buildGraph(node.right);
        }
    }

    private TreeNode findNode(TreeNode root, int val) {
        if (root == null) return null;
        if (root.val == val) return root;
        TreeNode left = findNode(root.left, val);
        if (left != null) return left;
        return findNode(root.right, val);
    }

    private static class DirNode {
        String dir;
        TreeNode node;

        DirNode(String dir, TreeNode node) {
            this.dir = dir;
            this.node = node;
        }
    }

    private static class Pair {
        TreeNode node;
        String path;

        Pair(TreeNode node, String path) {
            this.node = node;
            this.path = path;
        }
    }
}

```

[2603. Collect Coins in a Tree](https://leetcode.com/problems/collect-coins-in-a-tree/)

{% tabs %}
{% tab title="First Tab" %}

#### **Approach**

1. **Prune all useless leaf nodes recursively:**
   * Start by removing leaf nodes that do not contain coins.
   * When you remove a leaf, its parent might become a leaf.
   * If that new leaf also has no coin, remove it as well.
   * Repeat this process until all remaining leaves have coins.
2. **Simulate collecting coins from grandparent nodes:**
   * Once only coin-containing leaves remain, we assume the coins can be collected from 2 hops away.
   * So, we remove the **leaves and their direct parents**, since we don’t need to walk all the way to the leaves.
3. **Count remaining edges:**
   * After the pruning steps, count the remaining edges.
   * Since we count both directions (a → b and b → a), we multiply the remaining edge count by 2.

***

#### **Complexity**

* **Time Complexity:** `O(n)` — each node and edge is processed at most a few times.
* **Space Complexity:** `O(n)` — for adjacency lists, degree counts, and queues.

```cpp
class Solution {
public:
    int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
        int n = coins.size();
        vector<set<int>> graph(n);

        // Build the adjacency list
        for (const auto& e : edges) {
            graph[e[0]].insert(e[1]);
            graph[e[1]].insert(e[0]);
        }

        queue<int> leaves;
        int totalEdges = edges.size() * 2;
        int deletedEdges = 0;

        // Remove all leaves with no coins
        for (int i = 0; i < n; ++i) {
            if (graph[i].size() == 1 && coins[i] == 0) {
                leaves.push(i);
            }
        }

        while (!leaves.empty()) {
            int leaf = leaves.front();
            leaves.pop();

            if (graph[leaf].empty()) continue;  // Already removed

            int parent = *graph[leaf].begin();

            graph[parent].erase(leaf);
            graph[leaf].erase(parent);
            deletedEdges += 2;
            if (graph[parent].size() == 1) {
            // If the parent becomes a leaf and has no coin, schedule it for removal
            if (graph[parent].size() == 1 && coins[parent] == 0) {
                leaves.push(parent);
            }
        }
            }

            // If the parent becomes a leaf and has no coin, schedule it for removal
            if (graph[parent].size() == 1 && coins[parent] == 0) {
                leaves.push(parent);
            }
        }

        // Collect remaining leaves (they must have coins)
        for (int i = 0; i < n; ++i) {
            if (graph[i].size() == 1) {
                leaves.push(i);
            }
        }

        // Remove leaves and their immediate parents (2 steps)
        for (int step = 0; step < 2; ++step) {
            int size = leaves.size();
            while (size--) {
                int leaf = leaves.front();
                leaves.pop();

                if (graph[leaf].empty()) continue;

                int parent = *graph[leaf].begin();

                graph[parent].erase(leaf);
                graph[leaf].erase(parent);
                deletedEdges += 2;

                if (graph[parent].size() == 1) {
                    leaves.push(parent);
                }
            }
        }
        return totalEdges - deletedEdges;
    }
};
```

{% endtab %}

{% tab title="Second Tab" %}

```cpp
int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
    int n = coins.size();
    vector<vector<int>> adj(n);  // Adjacency list

    // Build the graph
    for (const auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }

    vector<int> degree(n), steps(n, 30000);  // degree: number of neighbors; steps: pruning marker
    vector<int> queue;

    // Initialize degrees and identify leaf nodes
    for (int i = 0; i < n; ++i) {
        degree[i] = adj[i].size();
        if (degree[i] == 1) {
            queue.push_back(i);
        }
    }

    int remainingNodes = n;

    // Prune nodes from the leaves inward
    while (!queue.empty()) {
        int node = queue.back(); queue.pop_back();

        if (--steps[node]) {  // If this node can still be removed
            --remainingNodes;
            for (int neighbor : adj[node]) {
                // Propagate step value: 2 if coin exists, otherwise large number
                steps[neighbor] = min(steps[neighbor], min(steps[node], coins[node] ? 2 : 30000));
                if (--degree[neighbor] == 1) {
                    queue.push_back(neighbor);
                }
            }
        }
    }

    // Final result: number of remaining edges * 2
    return 2 * max(0, remainingNodes - 1);
}

```

{% endtab %}
{% endtabs %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://howardyangemail.gitbook.io/decode-leetcode/bfs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.