https://leetcode.com/problems/pacific-atlantic-water-flow/

// 其实，这道题目可以参考前面的那道：Trapping Rain Water II

// 可以看我blog上面的解法：

// http://www.cnblogs.com/charlesblc/p/5920258.html

// 注意Java set的操作，retainAll 交集，removeAll差集

// 开始set里面放的是int[]，但是发现比较的时候，都被认为不一样，所以需要换成Block

// 第一次提交还报了一个Runtime Error，因为没有考虑row或者column为0的情况

public class Solution {

    private class Block {

        public int row;

        public int col;

        public int height;

        public Block(int r, int c, int h) {

            row = r;

            col = c;

            height = h;

        }

        public int hashCode() {

            return row + col + height;

        }

        public boolean equals(Object obj) {

            if (obj instanceof Block) {

                Block bk = (Block)obj;

                return bk.row == row && bk.col == col;

            }

            return false;

        }

    }

    public List<int[]> pacificAtlantic(int[][] matrix) {

        List<int[]> ret = new ArrayList<int[]>();

        int r = matrix.length;

        if (r == 0) {

            return ret;

        }

        int c = matrix[0].length;

        if (c == 0) {

            return ret;

        }

        Set<Block> pSt = new HashSet<Block>();

        Set<Block> aSt = new HashSet<Block>();

        Queue<Block> qe = new PriorityQueue<Block>(1,

                new Comparator<Block>() {

                    @Override

                    public int compare(Block o1, Block o2) {

                        return o1.height - o2.height;

                    }

                }

        );

        boolean[][] visited = new boolean[r][c];

        int[][] dirs = {{-1,0}, {0, 1}, {1, 0}, {0, -1}};

        for (int i=0; i<r; i++) {

            Block bk = new Block(i, 0, matrix[i][0]);

            pSt.add(bk);

            //System.out.printf("add pset: %d, %d\n", tmp[0], tmp[1]);

            qe.offer(bk);

            visited[i][0] = true;

        }

        for (int i=0; i<c; i++) {

            Block bk = new Block(0, i, matrix[0][i]);

            pSt.add(bk);

            //System.out.printf("add pset: %d, %d\n", tmp[0], tmp[1]);

            qe.offer(bk);

            visited[0][i] = true;

        }

        while (!qe.isEmpty()) {

            Block bk = qe.poll();

            for (int i=0; i<4; i++) {

                int nr = bk.row + dirs[i][0];

                int nc = bk.col + dirs[i][1];

                if (nr < 0 || nr >= r || nc < 0 || nc >= c || visited[nr][nc]) {

                    continue;

                }

                visited[nr][nc] = true;

                if (matrix[nr][nc] >= bk.height) {

                    Block nbk = new Block(nr, nc, matrix[nr][nc]);

                    pSt.add(nbk);

                    //System.out.printf("add pset new: %d, %d\n", tmp[0], tmp[1]);

                    qe.offer(nbk);

                }

            }

        }

        // 重新初始化，计算atlantic

        qe.clear();

        visited = new boolean[r][c];

        for (int i=0; i<r; i++) {

            Block bk = new Block(i, c-1, matrix[i][c-1]);

            aSt.add(bk);

            //System.out.printf("add aset: %d, %d\n", tmp[0], tmp[1]);

            qe.offer(bk);

            visited[i][c-1] = true;

        }

        for (int i=0; i<c; i++) {

            Block bk = new Block(r-1, i, matrix[r-1][i]);

            aSt.add(bk);

            //System.out.printf("add aset: %d, %d\n", tmp[0], tmp[1]);

            qe.offer(bk);

            visited[r-1][i] = true;

        }

        while (!qe.isEmpty()) {

            Block bk = qe.poll();

            for (int i=0; i<4; i++) {

                int nr = bk.row + dirs[i][0];

                int nc = bk.col + dirs[i][1];

                if (nr < 0 || nr >= r || nc < 0 || nc >= c || visited[nr][nc]) {

                    continue;

                }

                visited[nr][nc] = true;

                if (matrix[nr][nc] >= bk.height) {

                    Block nbk = new Block(nr, nc, matrix[nr][nc]);

                    aSt.add(nbk);

                    //System.out.printf("add aset new: %d, %d\n", tmp[0], tmp[1]);

                    qe.offer(nbk);

                }

            }

        }

        //System.out.printf("pset length: %d\n", pSt.size());

        //System.out.printf("aset length: %d\n", aSt.size());

        pSt.retainAll(aSt);

        System.out.printf("set length: %d\n", pSt.size());

        Iterator itr = pSt.iterator();

        while (itr.hasNext()) {

            Block bk = (Block)itr.next();

            int[] val = {bk.row, bk.col};

            ret.add(val);

        }

        return ret;

    }

}