leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0329.cpp (2079B)

0 class Solution { 1 public: 2 int longestIncreasingPath(const vector<vector<int>> &matrix) const { 3 const int n = size(matrix), m = size(matrix[0]); 4 5 static const int offset[] = {-1, 0, 1, 0, -1}; 6 const auto valid = [&](int i, int j) { return i >= 0 && i < n && j >= 0 && j < m; }; 7 8 static int dp[201][201]; 9 memset(dp, 0xFF, sizeof(dp)); 10 11 int res = 0; 12 stack<tuple<int, int>> st; 13 for (int i = 0; i < n; i++) { 14 for (int j = 0; j < m; j++) { 15 if (dp[i][j] != -1) continue; 16 17 st.emplace(i, j); 18 while (!st.empty()) { 19 if (get<0>(st.top()) != -1) { 20 const auto [i, j] = st.top(); 21 if (dp[i][j] != -1) { 22 st.pop(); 23 continue; 24 } 25 26 dp[i][j] = -3; 27 st.emplace(-1, -1); 28 for (int k = 0; k < 4; k++) { 29 const int a = i + offset[k + 1]; 30 const int b = j + offset[k]; 31 32 if (!valid(a, b) || matrix[i][j] >= matrix[a][b]) continue; 33 if (dp[a][b] != -1) continue; 34 st.emplace(a, b); 35 dp[i][j] = -2; 36 } 37 38 continue; 39 } 40 41 st.pop(); 42 const auto [i, j] = st.top(); 43 st.pop(); 44 45 int res = 0; 46 for (int k = 0; k < 4; k++) { 47 const int a = i + offset[k + 1]; 48 const int b = j + offset[k]; 49 50 if (!valid(a, b) || matrix[i][j] >= matrix[a][b]) continue; 51 res = max(res, dp[a][b]); 52 } 53 54 dp[i][j] = res + 1; 55 } 56 57 res = max(res, dp[i][j]); 58 } 59 } 60 61 return res; 62 } 63 };