public class Lcp44 {

    Set<Integer> set;

    /**
     * 开幕式火焰
     *
     * @param root
     * @return
     */
    public int numColor(TreeNode root) {
        set = new HashSet<>();
        dfs(root);
        return set.size();
    }

    public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        set.add(root.val);
        dfs(root.left);
        dfs(root.right);
    }
}

class Solution {
    
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    List<int[]> ans;
    Set<String> mem;
    boolean[][] global;
    int[] p;

    public int[][] bicycleYard(int[] position, int[][] terrain, int[][] obstacle) {
        ans = new ArrayList<>();
        mem = new HashSet<>();
        global = new boolean[terrain.length][terrain[0].length];
        p = position;
        bfs(1, position[0], position[1], terrain, obstacle);
        int[][] res = new int[ans.size()][2];
        for (int i = 0; i < ans.size(); i++) {
            res[i] = ans.get(i);
        }
        Arrays.sort(res, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return Integer.compare(o1[1], o2[1]);
            } else {
                return Integer.compare(o1[0], o2[0]);
            }
        });
        return res;
    }

    public void bfs(int curr, int x, int y, int[][] terrain, int[][] obstacle) {
        if (x >= 0 && y >= 0 && x < terrain.length && y < terrain[0].length) {
            for (int i = 0; i < 4; i++) {
                int newX = x + dx[i];
                int newY = y + dy[i];
                if (newX >= 0 && newY >= 0 && newX < terrain.length && newY < terrain[0].length) {
                    int next = curr + terrain[x][y] - terrain[newX][newY] - obstacle[newX][newY];
                    // i, j, v 作为唯一 key
                    String k = newX + "-" + newY + "-" + next;
                    if (mem.contains(k)) {
                        continue;
                    }
                    mem.add(k);
                    if (next >= 1) {
                        if (next == 1 && (newX != p[0] || newY != p[1]) && !global[newX][newY]) {
                            global[newX][newY] = true;
                            ans.add(new int[]{newX, newY});
                        }
                        bfs(next, newX, newY, terrain, obstacle);
                    }
                }
            }
        }
    }
}