class Solution
{
public:
    static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int m, n;
    int longestIncreasingPath(vector<vector<int>> &matrix)
    {
        if (matrix.size() == 0 || matrix[0].size() == 0)
        {
            return 0;
        }
        m = matrix.size();
        n = matrix[0].size();
        int res = 0;
        auto memo = vector<vector<int>>(m, vector<int>(n, 0));
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (memo[i][j])
                    res = max(res, memo[i][j]);
                else
                    res = max(res, dfs(i, j, matrix, memo));
            }
        }
        return res;
    }

    int dfs(int i, int j, vector<vector<int>> &matrix, vector<vector<int>> &memo)
    {
        int temp = 1;
        for (int k = 0; k < 4; ++k)
        {
            int x = i + dirs[k][0];
            int y = j + dirs[k][1];
            if ((x >= 0) && (x < m) && (y >= 0) && (y < n) && (matrix[i][j] < matrix[x][y]))
            {
                if (memo[x][y])
                    temp = max(temp, memo[x][y] + 1);
                else
                    temp = max(temp, dfs(x, y, matrix, memo) + 1);
            }
        }
        memo[i][j] = temp;
        return temp;
    }
};