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