class Solution { public: vector<pair<int, int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int longestIncreasingPath(vector<vector<int>>& matrix) { int m = matrix.size(), n = m? matrix[0].size(): 0, res = 0; unordered_map<int, int> map; for(int i = 0; i < m; ++i) for(int j = 0; j < n; ++j) res = max(res, dfs(matrix, map, i, j)); return res; } private: int dfs(vector<vector<int>>& matrix, unordered_map<int, int>& map, int x, int y) { int m = matrix.size(), n = matrix[0].size(), len = 1; if(map.count(x * n + y))return map[x * n + y]; for(auto& dir : dirs) { int i = x + dir.first, j = y + dir.second; if(i >= 0 && i < m && j >= 0 && j < n && matrix[i][j] > matrix[x][y]) len = max(len, dfs(matrix, map, i, j) + 1); } map[x * n + y] = len; return len; } };