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