leetcode

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 };