🌕🌗 417. 太平洋大西洋水流问题

难度: 🌕🌗

问题描述

---

解法

class Solution {
    int[][] board;
    int row;
    int col;
    int[][] heights;
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        // 思路：
        // 回溯
        // 从边界出发，往高的方向走，走过的路径进行染色
        row = heights.length;
        col = heights[0].length;
        board = new int[row][col]; // 1 - 太平洋；2 - 大西洋；3 - 全部
        this.heights = heights;
        List<List<Integer>> res = new ArrayList<>();
        
        for(int i = 0; i < row; i ++) {
            if(board[i][0] == 1) {
                continue;
            } else {
                mySol(i, 0, 1, i, 0);
            }
        }
        for(int j = 1; j < col; j ++) {
            if(board[0][j] == 1) {
                continue;
            }
            mySol(0, j, 1, 0, j);
        }
        // 大西洋
        for(int i = 0; i < row; i ++) {
            if(board[i][col - 1] == 2) {
                continue;
            } 
            mySol(i, col - 1, 2, i, col - 1);
        }
        for(int j = 0; j < col - 1; j ++) {
            if(board[row - 1][j] == 2) {
                continue;
            }
            mySol(row - 1, j, 2, row - 1, j);
        }
        // 遍历
        for(int i = 0; i < row; i ++) {
            for(int j = 0; j < col; j ++) {
                if(board[i][j] == 3) {
                    List<Integer> list = new ArrayList<>();
                    list.add(i);
                    list.add(j);
                    res.add(list);
                }
            }
        }
        return res;
    }

    private void mySol(int i, int j, int flag, int pi, int pj) {
        // 递归终止条件
        if(!isValid(i, j)) {
            return;
        }
        if(heights[i][j] < heights[pi][pj]) {
            return; // 只能往高处走
        }
        if(board[i][j] == flag || board[i][j] == 3) {
            return; // 已经走过
        }
        // 染色当前单元格
        if(board[i][j] == 0) {
            board[i][j] = flag;
        } else {
            board[i][j] = 3;
        }
        // System.out.println(i + ":" + j + " " + board[i][j] + " " + pi + ":" + pj);
        // 往四个方向回溯
        mySol(i - 1, j, flag, i, j);
        mySol(i + 1, j, flag, i, j);
        mySol(i, j - 1, flag, i, j);
        mySol(i, j + 1, flag, i, j);
    }

    private boolean isValid(int i, int j) {
        if(i < 0 || i >= row) {
            return false;
        }
        if(j < 0 || j >= col) {
            return false;
        }
        return true;
    }
}

---

输出