BFS找最短路徑用level order，有模版。
圖上的搜素記得考慮用戶visited數(shù)組

visited[][] 
queue.add(start)
visited.add(start)
while(queue not empty) {
  int size = queue.size
  for (0 - size) {
  }
}

675. Cut Off Trees for Golf Event

You are asked to cut off trees in a forest for a golf event. The forest is represented as a non-negative 2D map, in this map:

0 represents the obstacle can't be reached.
1 represents the ground can be walked through.
The place with number bigger than 1 represents a tree can be walked through, and this positive number represents the tree's height.
You are asked to cut off all the trees in this forest in the order of tree's height - always cut off the tree with lowest height first. And after cutting, the original place has the tree will become a grass (value 1).

You will start from the point (0, 0) and you should output the minimum steps you need to walk to cut off all the trees. If you can't cut off all the trees, output -1 in that situation.

You are guaranteed that no two trees have the same height and there is at least one tree needs to be cut off.

Example 1:
Input:
[
[1,2,3],
[0,0,4],
[7,6,5]
]
Output: 6

這道題沒做出來的原因是沒想清楚如何手動算出結(jié)果。從起點開始走，找出當前最矮的樹，走過去，再找到第二矮的樹走過去，累加步數(shù)。所以想到用heap找到當前最矮的樹，然后用bfs算出當前點到樹的最短路徑。起點也要加到隊列里?？惩瓴挥眯薷膫鬟M來的list of list，比如從4走到7，說明沒有高度是5，6的樹還存在了。

class Solution {
    // move 4 directions
    int[] dX = {0, 0, -1, 1};
    int[] dY = {1, -1, 0 , 0};
    public int cutOffTree(List<List<Integer>> forest) {
        int m = forest.size();
        int n = forest.get(0).size();
        Comparator<Position> com = (p1, p2) -> p1.val - p2.val;
        PriorityQueue<Position> queue = new PriorityQueue<>(com); // every time minimum value is poped
        // add all postion and its value into queue
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // not add (0, 0) into queue
                if (forest.get(i).get(j) > 1) {
                    Position p = new Position(i, j, forest.get(i).get(j));
                    queue.add(p);
                }
            }
        }
        int res = 0;
        // start from 0, 0
        Position start = new Position(0, 0, 0);
        while (!queue.isEmpty()) {
            Position end = queue.poll();
            int steps = helper(start, end, forest, m, n);
            if (steps < 0) {
                return -1;
            }
            res += steps;
            start = end;
        }
        
        return res;
    }
    // return the minumum steps from start to end, using BFS
    private int helper(Position start, Position end, List<List<Integer>> forest, int m, int n) {
        // record visited array, using 2-d array
        int[][] visited = new int[m][n];
        Queue<Position> queue = new LinkedList<>();
        queue.add(start);
        visited[start.x][start.y] = 1;
        int step = 0;        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Position cur = queue.poll();
                if (cur.x == end.x && cur.y == end.y) {
                    return step;
                }
                // go to four directions
                for (int j = 0; j < 4; j++) {
                    // add qulified position into queue
                    int new_x = cur.x + dX[j], new_y = cur.y + dY[j];
                    if (new_x >= 0 && new_x < m && new_y >= 0 && new_y < n
                        && forest.get(new_x).get(new_y) > 0
                        && visited[new_x][new_y] != 1) {
                        Position p = new Position(new_x, new_y, forest.get(new_x).get(new_y));
                        queue.add(p);
                        visited[new_x][new_y] = 1;
                    }
                }
            }
            step++;
        }
        return -1;
    }

}

class Position {
    int x; 
    int y;
    int val;
    public Position (int x, int y, int val) {
        this.x = x;
        this.y = y;
        this.val = val;
    }
}

742. Closest Leaf in a Binary Tree

見DFS

286. Walls and Gates

-1 - A wall or an obstacle.
0 - A gate.
INF - Infinity means an empty room.
For example, given the 2D grid:
INF -1 0 INF
INF INF INF -1
INF -1 INF -1
0 -1 INF INF
After running your function, the 2D grid should be:
3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4

DFS BFS都可以做，需要注意的是以門為起點去向下延伸，而不是以房間開始

class Solution {
    public void wallsAndGates(int[][] rooms) {
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < rooms.length; i++) {
            // push gate into queue
            for (int j = 0; j < rooms[i].length; j++) {
                if (rooms[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                }
            }
        }
        int[] dx = {0, 0, -1, 1};
        int[] dy = {1, -1, 0, 0};
        while (!queue.isEmpty()) {
            int[] cor = queue.poll();
            int i = cor[0], j = cor[1];
            for (int idx = 0; idx < 4; idx++) {
                if (i + dx[idx] >= 0 && i + dx[idx] <= rooms.length - 1 && j + dy[idx] >= 0 && j +                                                  dy[idx] <= rooms[0].length - 1 && rooms[i + dx[idx]][j + dy[idx]] == Integer.MAX_VALUE) {
                    rooms[i + dx[idx]][j + dy[idx]] = rooms[i][j] + 1;
                    queue.offer(new int[]{i + dx[idx], j + dy[idx]});
                }
            }
        }
    }
}