leetcode 417. Pacific Atlantic Water Flow

原題:Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent,the“Pacific ocean”touches the left and top edges of the matrix and the“Atlantic ocean”touches the right and bottom edges.
Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.
Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.
Note:

The order of returned grid coordinates does not matter.
Both m and n are less than 150.

Example:
Given the following 5x5 matrix:
Pacific ~ ~ ~ ~ ~ ~ 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 * * * * * * Atlantic
Return:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).
テーマは,各位置matrix[x][y]はこの点の高さを表し,各点は自分の高さに等しい点または低い点に流れることができると述べている.上、左はPacificを代表して、右、下はAtlanticを代表して、このmatrixの中で同時に太平洋、大西洋の座標集に流れることができることを求めます.一般的にDFSの解法を見ると思いますが、私は初めて題意を理解し間違えて、matrixの中のすべての点を遍歴して、彼が2つの海に着くことができるかどうかを見ました.最後に、タイムアウトして、もっと完璧なアルゴリズムを考えます.Java BFS

public class Solution {
    int[][] dics = new int[][]{{1,0}, {0,1},{-1,0}, {0,-1}};
    public static void main(String[] args) {
        // TODO Auto-generated method stub

    }
    //             BFS   DFS    ，
    //          
    public List<int[]> pacificAtlantic(int[][] matrix) {
        List<int[]> res = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return res;
        }
        int rows = matrix.length;
        int cols = matrix[0].length;
        boolean[][] pacific =  new boolean[rows][cols]; //         pacific
        boolean[][] atlantic = new boolean[rows][cols]; //        atlantic
        Stack<int[]> visitPac = new Stack<>();
        Stack<int[]> visitAtlan = new Stack<>();
        for (int i = 0; i < rows; i++) {
            pacific[i][0] = true;
            visitPac.push(new int[]{i,0});
            atlantic[i][cols - 1] = true;
            visitAtlan.push(new int[]{i,cols - 1});
        }
        for (int j = 0; j < cols; j++) {
            pacific[0][j] = true;
            visitPac.push(new int[]{0,j});
            atlantic[rows - 1][j] = true;
            visitAtlan.push(new int[]{rows - 1, j});
        }
        bfs(matrix, visitPac, pacific);
        bfs(matrix, visitAtlan, atlantic);
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    res.add(new int[]{i,j});
                }
            }
        }
        return res;
    }
    public void bfs(int[][] matrix, Stack<int[]> stack, boolean[][] visited) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        while (!stack.isEmpty()) {
            int[] idx = stack.pop();
            for (int[] dic:dics) {
                int x = idx[0] + dic[0];
                int y = idx[1] + dic[1];
                if (x < 0 || x >= rows || y < 0 || y >= cols || visited[x][y] || matrix[x][y] < matrix[idx[0]][idx[1]]) {
                    continue;
                }
                visited[x][y] = true;
                stack.push(new int[]{x,y});
            }
        }
    }
}

後で他の人が提出したDFSバージョンの答えを見て、DFSはもっと理解しやすいです.

import java.util.ArrayList;
import java.util.List;

/**
* @author    : coderlong
* @version     ：2018 4 27    2:59:28
*    : 
*/
public class leetcode417_Pactic_Atlantic_water_Flow2 {
    public int[][] dics = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    public static void main(String[] args) {
        // TODO Auto-generated method stub

    }
    public List<int[]> pacificAtlantic(int[][] matrix) {
        List<int[]> res = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return res;
        }
        int rows = matrix.length;
        int cols = matrix[0].length;

        boolean[][] pacific = new boolean[rows][cols];
        boolean[][] atlantic = new boolean[rows][cols];
        //  Integer.MIN_VALUE           ，             visit  
        for (int i = 0; i < rows; i++) {
            dfs(matrix, Integer.MIN_VALUE, i, 0, pacific);
            dfs(matrix, Integer.MIN_VALUE, i, cols - 1, atlantic);
        }
        for (int j = 0; j < cols; j++) {
            dfs(matrix, Integer.MIN_VALUE, 0, j, pacific);
            dfs(matrix, Integer.MIN_VALUE, rows - 1, j, atlantic);
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    res.add(new int[]{i,j});
                }
            }
        }
        return res;
    }
    public void dfs(int[][] matrix, int height, int x, int y, boolean[][]visit) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        // x y    ，           
        if (x <0 || x >= rows || y < 0 || y >= cols || visit[x][y] || matrix[x][y] < height) {
            return ;
        }
        visit[x][y] = true; // (x,y)     visit  
        for (int[] cur : dics) {
            dfs(matrix, matrix[x][y], x + cur[0], y + cur[1], visit);
        }
    }

}