Summary of force deduction method 417- Pacific Atlantic current problems

  Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ： Power button

describe ：

There is one m × n Rectangular Island , And The Pacific Ocean and The Atlantic ocean adjacent . “ The Pacific Ocean ”  On the left and upper boundary of the continent , and “ The Atlantic ocean ” On the right and lower boundaries of the continent .

The island is divided into a grid of square cells . Given a m x n The integer matrix of  heights , heights[r][c]  Representation coordinates (r, c) Upper cell Height above sea level .

There is more rain on the island , If the height of adjacent cells Less than or equal to The height of the current cell , The rain can go straight north 、 south 、 In the east 、 West flow to adjacent cells . Water can flow into the ocean from any cell near the ocean .

return Grid coordinates result  Of 2D list , among  result[i] = [ri, ci]  Indicates that rainwater can be extracted from the cell (ri, ci) flow The Pacific and Atlantic .

Example 1：

Input : heights = [[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]]
Output : [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Example 2：

Input : heights = [[2,1],[1,2]]
Output : [[0,0],[0,1],[1,0],[1,1]]
 

Tips ：

m == heights.length
n == heights[r].length
1 <= m, n <= 200
0 <= heights[r][c] <= 105

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/pacific-atlantic-water-flow
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  General idea , First find the one that can flow to the Pacific Ocean , Then I'm looking for something that can flow to the Atlantic .
*  How to find the water flowing to the Pacific Ocean pacificset？ You can use recursion , First from x=0 and y=0 Start with two lines . Look up, down, left and right , If it is already in the collection, skip , Otherwise, judge its sea level height value Compliance , If yes, join and continue recursion .
*  Similarly, find the collection flowing to the Atlantic atlanticset.
*  Two set The collection holds the areas flowing to the Pacific and Atlantic respectively , Then taking the intersection is the result we want .
*  Of course, there is a small problem with this solution , After recursive judgment , Because every time there is no direction, you can judge up, down, left and right , The probability of repeated search is high .
*  A more efficient solution to fatigue is to walk step by step , That is, first find a collection that can reach the seaside , Find the second step to the beach , Then three steps , Continue recursion .

Code ：

public class Solution417 {

    Set<String> pacificset = new HashSet<>();
    Set<String> atlanticset = new HashSet<>();

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        // On 
        for (int x = 0; x < heights[0].length; x++) {
            String key = getKey(x, 0);
            pacificset.add(key);
            findInflow(heights, pacificset, heights[0][x], key, x, 1);
        }
        // Left 
        for (int y = 0; y < heights.length; y++) {
            String key = getKey(0, y);
            pacificset.add(key);
            findInflow(heights, pacificset, heights[y][0], key, 1, y);
        }
        // Next 
        for (int x = 0; x < heights[0].length; x++) {
            String key = getKey(x, heights.length - 1);
            atlanticset.add(key);
            findInflow(heights, atlanticset, heights[heights.length - 1][x], key, x, heights.length - 2);
        }
        // Right 
        for (int y = 0; y < heights.length; y++) {
            String key = getKey(heights[0].length - 1, y);
            atlanticset.add(key);
            findInflow(heights, atlanticset, heights[y][heights[0].length - 1], key, heights[0].length - 2, y);
        }

        List<List<Integer>> result = new ArrayList<>();
        for (String key : pacificset) {
            if (!atlanticset.contains(key)) {
                continue;
            }
            String[] s = key.split("_");
            List<Integer> list = new ArrayList<>();
            for (String str : s) {
                list.add(Integer.parseInt(str));
            }
            result.add(list);
        }
        return result;
    }

    private void findInflow(int[][] heights, Set<String> set, int oldValue, String oldKey, int x, int y) {
        if (y < 0 || x < 0 || x >= heights[0].length || y >= heights.length) {
            return;
        }
        String key = getKey(x, y);
        if (set.contains(key)) {
            return;
        }
        int value = heights[y][x];
        if (oldValue > value) {
            return;
        }
        set.add(key);
        findInflow(heights, set, value, key, x + 1, y);
        findInflow(heights, set, value, key, x - 1, y);
        findInflow(heights, set, value, key, x, y + 1);
        findInflow(heights, set, value, key, x, y - 1);
    }

    private String getKey(int x, int y) {
        return y + "_" + x;
    }

}