package leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.Set;

/**
 * https://leetcode.com/problems/pacific-atlantic-water-flow/
 */
public class Problem417 {
    public List<int[]> pacificAtlantic(int[][] matrix) {
        List<int[]> result = new ArrayList<>();
        if (matrix.length == 0) {
            return result;
        }
        int maxRow = matrix.length;
        int maxCol = matrix[0].length;
        for (int row = 0; row < maxRow; row++) {
            for (int col = 0; col < maxCol; col++) {
                boolean found = pacificAtlantic(matrix, maxRow, maxCol, row, col);
                if (found) {
                    result.add(new int[]{row, col});
                }
            }
        }
        return result;
    }

    private static boolean pacificAtlantic(int[][] matrix, int maxRow, int maxCol,
                                           int row, int col) {
        boolean pacific = false;
        boolean atlantic = false;
        Set<RowCol> visited = new HashSet<>();
        LinkedList<RowCol> queue = new LinkedList<>();
        RowCol start = new RowCol(row, col);
        queue.add(start);
        visited.add(start);
        while (!queue.isEmpty()) {
            RowCol rc = queue.remove();
            if (rc.row < 0 || rc.row >= maxRow || rc.col < 0 || rc.col >= maxCol) {
                if (rc.row < 0 || rc.col < 0) {
                    pacific = true;
                }
                if (rc.row >= maxRow || rc.col >= maxCol) {
                    atlantic = true;
                }
                if (pacific && atlantic) {
                    return true;
                }
            } else {
                int val = matrix[rc.row][rc.col];
                RowCol up = new RowCol(rc.row - 1, rc.col);
                if (!visited.contains(up)) {
                    if (up.row < 0 || matrix[up.row][up.col] <= val) {
                        queue.add(up);
                        visited.add(up);
                    }
                }
                RowCol right = new RowCol(rc.row, rc.col + 1);
                if (!visited.contains(right)) {
                    if (right.col >= maxCol || matrix[right.row][right.col] <= val) {
                        queue.add(right);
                        visited.add(right);
                    }
                }
                RowCol down = new RowCol(rc.row + 1, rc.col);
                if (!visited.contains(down)) {
                    if (down.row >= maxRow || matrix[down.row][down.col] <= val) {
                        queue.add(down);
                        visited.add(down);
                    }
                }
                RowCol left = new RowCol(rc.row, rc.col - 1);
                if (!visited.contains(left)) {
                    if (left.col < 0 || matrix[left.row][left.col] <= val) {
                        queue.add(left);
                        visited.add(left);
                    }
                }
            }
        }
        return pacific && atlantic;
    }

    private static class RowCol {
        private final int row;
        private final int col;

        public RowCol(int row, int col) {
            this.row = row;
            this.col = col;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            RowCol rowCol = (RowCol) o;
            return row == rowCol.row &&
                col == rowCol.col;
        }

        @Override
        public int hashCode() {
            return Objects.hash(row, col);
        }

        @Override
        public String toString() {
            return "(" + row + ", " + col + ")";
        }
    }

    public static void main(String[] args) {
        Problem417 prob = new Problem417();
        // [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]
        prob.pacificAtlantic(new int[][]{
            {1, 2, 2, 3, 5},
            {3, 2, 3, 4, 4},
            {2, 4, 5, 3, 1},
            {6, 7, 1, 4, 5},
            {5, 1, 1, 2, 4}
        }).forEach(e -> {
            System.out.print("[" + e[0] + ", " + e[1] + "] ");
        });
        System.out.println();
    }
}

@@ -506,32 +506,76 @@
 trix%5B0%5D.length;%0A
+        Set%3CRowCol%3E memo = new HashSet%3C%3E();%0A
         for (int
@@ -732,32 +732,38 @@
 maxCol, row, col
+, memo
 );%0A             
@@ -774,24 +774,76 @@
 f (found) %7B%0A
+                    memo.add(new RowCol(row, col));%0A
             
@@ -1089,32 +1089,50 @@
 int row, int col
+, Set%3CRowCol%3E memo
 ) %7B%0A        bool
@@ -2096,32 +2096,148 @@
 .col%5D %3C= val) %7B%0A
+                        if (memo.contains(up)) %7B%0A                            return true;%0A                        %7D%0A
                 
@@ -2529,32 +2529,151 @@
 .col%5D %3C= val) %7B%0A
+                        if (memo.contains(right)) %7B%0A                            return true;%0A                        %7D%0A
                 
@@ -2966,32 +2966,150 @@
 .col%5D %3C= val) %7B%0A
+                        if (memo.contains(down)) %7B%0A                            return true;%0A                        %7D%0A
                 
@@ -3394,32 +3394,150 @@
 .col%5D %3C= val) %7B%0A
+                        if (memo.contains(left)) %7B%0A                            return true;%0A                        %7D%0A
                 
@@ -4320,602 +4320,8 @@
    %7D
-%0A%0A        @Override%0A        public String toString() %7B%0A            return %22(%22 + row + %22, %22 + col + %22)%22;%0A        %7D%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem417 prob = new Problem417();%0A        // %5B%5B0, 4%5D, %5B1, 3%5D, %5B1, 4%5D, %5B2, 2%5D, %5B3, 0%5D, %5B3, 1%5D, %5B4, 0%5D%5D%0A        prob.pacificAtlantic(new int%5B%5D%5B%5D%7B%0A            %7B1, 2, 2, 3, 5%7D,%0A            %7B3, 2, 3, 4, 4%7D,%0A            %7B2, 4, 5, 3, 1%7D,%0A            %7B6, 7, 1, 4, 5%7D,%0A            %7B5, 1, 1, 2, 4%7D%0A        %7D).forEach(e -%3E %7B%0A            System.out.print(%22%5B%22 + e%5B0%5D + %22, %22 + e%5B1%5D + %22%5D %22);%0A        %7D);%0A        System.out.println();
 %0A   

Solve problem 417