Longest Increasing Path in a Matrix -- LeetCode

[Question]

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return 4
The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

[Analysis]
Using DFS from each position of the matrix, travel on each possible paths, and get the maximum length that the position can reach. The length of path in each position can be reused. Therefore, an additional matrix is used to record the length information of each position. The time complexity and space complexity are both O(MxN), the size of matrix.

[Solution]
class Solution {
    vector<pair<int,int>> dd={{-1,0},{1,0},{0,1},{0,-1}};
 
    int searchPath(vector<vector<int>>& matrix, int i, int j, vector<vector<int>>& lens) {
        if (lens[i][j]!=0) return lens[i][j];
     
        int len=0;
        int temp = matrix[i][j];
        matrix[i][j] = INT_MIN;
        for (auto&d : dd) {
            int x = i+d.first, y=j+d.second;
            if (x>=0 && x<matrix.size() && y>=0 && y<matrix[0].size() && matrix[x][y]>temp) {
                len = max(len, searchPath(matrix, x, y, lens));
            }
        }
        matrix[i][j] = temp;
        lens[i][j] = 1 + len;
        return 1+len;
    }
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.empty()) return 0;
        vector<vector<int>> lens(matrix.size(), vector<int>(matrix[0].size(), 0));
     
        int res=1;
        for (int i=0; i<matrix.size(); i++) {
            for (int j=0; j< matrix[0].size(); j++) {
                res = max(res, searchPath(matrix, i, j, lens) );
            }
        }
        return res;
    }

};