/**
knakul853
**/
class Solution {
public:
    int dx[4] = {0, 0, -1, 1};
     int dy[4] = {1, -1, 0, 0};
    int longestIncreasingPath(vector<vector<int>>& matrix) {

        if( matrix.empty() || matrix[0].empty()) return 0;

        int n = (int)matrix.size();
        int m = (int)matrix[0].size();

        vector<vector<int>>dp(n, vector<int>(m, -1));

        int ans = 1;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                ans = max(ans, dfs(i, j, dp, matrix));
            }
        }

        return ans;
    }

    int dfs(int i, int j, vector<vector<int>>&dp, vector<vector<int>>& matrix)
    {
       int& ret = dp[i][j];

        if( ret != -1) return ret;

        ret = 0;

        for(int dir=0; dir<4; dir++ )
        {
            int nx = i + dx[dir];
            int ny = j + dy[dir];

            if( nx < 0 || ny < 0 || nx >= (int)dp.size() || ny >= (int)dp[0].size())continue;
            if(matrix[nx][ny] <= matrix[i][j]) continue;

              ret = max(ret, dfs(nx, ny, dp, matrix));

        }
        ret++;

        return ret;


    }
};