329. Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return4
The longest increasing path is[1, 2, 6, 9].

Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Return4
The longest increasing path is[3, 4, 5, 6]. Moving diagonally is not allowed.

S：记忆化搜索 O(mn)

len[i][j]表示以matrix[i][j]为起始点的最常增序列长度，对每个点进行dfs

    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if (m == 0) return 0;
        int n = matrix[0].size();
        len = vector<vector<int>>(m, vector<int>(n, 0));
        int result = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                result = max(result, getLen(matrix, i, j));
            }
        }
        return result;
    }

private:
    int getLen(vector<vector<int>>& matrix, int x, int y) {
        if (len[x][y] > 0) {
            return len[x][y];
        }
        len[x][y] = 1;
        vector<int> dx{0, 1, 0, -1};
        vector<int> dy{1, 0, -1, 0};
        int m = matrix.size(), n = matrix[0].size();
        for (int i = 0; i < 4; ++i) {
            int x1 = x + dx[i];
            int y1 = y + dy[i];
            if (x1 >= 0 && x1 < m && y1 >= 0 && y1 < n && matrix[x1][y1] > matrix[x][y]) {
                len[x][y] = max(len[x][y], 1 + getLen(matrix, x1, y1));
            }
        }
        return len[x][y];
    }
    vector<vector<int>> len;

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:

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

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).

S：记忆化搜索 + bit manipulation O(mn)

用flow[i][j]最后两位表示是否能流到pacific和altlantic

//注意有 runtime error
    vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
        vector<pair<int, int>> result;
        int m = matrix.size();
        if (m == 0) return result;
        int n = matrix[0].size();
        flow = vector<vector<int>>(m, vector<int>(n, -1));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (getFlow(matrix, i, j) == 3) {
                    result.push_back(make_pair(i, j));
                }
            }
        }
        return result;
    }

    int getFlow(vector<vector<int>>& matrix, int x, int y) {
        if (flow[x][y] >= 0) return flow[x][y];
        flow[x][y] == 0;
        int m = matrix.size();
        int n = matrix[0].size();
        if (x == 0 || y == 0) flow[x][y] |= 1;
        if (x == m - 1 || y == n - 1) flow[x][y] |= 2;
        vector<int> dx{0, 1, 0, -1};
        vector<int> dy{1, 0, -1, 0};
        for (int i = 0; i < 4; ++i) {
            int x1 = x + dx[i];
            int y1 = y + dy[i];
            if (x1 >= 0 && x1 < m && y1 >= 0 && y1 < n && matrix[x1][y1] <= matrix[x][y]) {
                int next = getFlow(matrix, x1, y1);
                flow[x][y] |= next;
            }
        }
        return flow[x][y];
    }

private:
    vector<vector<int>> flow;