aboutsummaryrefslogtreecommitdiff
path: root/longest_increasing_matrix_path.cpp
blob: 1ee5b99a6f7449e8b5eb8a9042a55e1ce4b26e5a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include "leetcode.h"

class Solution {
public:
  int longestIncreasingPath(vector<vector<int>> &matrix) {
    int rows = matrix.size(), cols = matrix[0].size();
    if (!rows)
      return 0;
    vector<vector<int>> dp(rows, vector<int>(cols, 0));
    function<int(int, int)> dfs = [&](int x, int y) {
      if (dp[x][y])
        return dp[x][y];
      vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
      for (auto &dir : dirs) {
        int x2 = x + dir[0], y2 = y + dir[1];
        if (x2 < 0 || x2 >= rows || y2 < 0 || y2 >= cols)
          continue;
        if (matrix[x2][y2] <= matrix[x][y])
          continue;
        dp[x][y] = max(dp[x][y], dfs(x2, y2));
      }
      return ++dp[x][y];
    };
    int ans = 0;
    for (int i = 0; i < rows; ++i)
      for (int j = 0; i < cols; ++j)
        ans = max(ans, dfs(i, j));
    return ans;
  }
};

int main() {}