class Solution
{
  public:
    int longestIncreasingPath(vector<vector<int>>& matrix)
    {
        if (matrix.empty())
            return 0;
        int m = matrix.size(), n = matrix[0].size();
        int max_len = 0;
        vector<vector<int>> visited(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (visited[i][j] != 0)
                    continue;
                dfs(matrix, visited, i, j, max_len);
            }
        }
        return max_len;
    }
    
    bool isValid(int x, int y, int m, int n)
    {
        return x >= 0 && y >= 0 && x < m && y < n;
    }

    int dfs(vector<vector<int>>& matrix, vector<vector<int>>& visited, int i, int j, int& max_len)
    {
        if (visited[i][j] != 0) {
            return visited[i][j];
        }
        int dir[4][2];
        dir[0] = {0, 1}; 
        dir[1] = {0, -1};
        dir[2] = {1, 0}; 
        dir[3] = {-1, 0};
        int m = matrix.size(), n = matrix[0].size();
        visited[i][j] = 1;
        for (int k = 0; k < 4; k++)
        {
            int x = i + dir[k][0], y = j + dir[k][1];
            if (isValid(x, y, m, n) && matrix[x][y] > matrix[i][j])
            {
                int len = dfs(matrix, visited, x, y, max_len);
                visited[i][j] = max(len + 1, visited[i][j]);
            }
        }
        max_len = max(max_len, visited[i][j]);
        return visited[i][j];
    }
};