<p>Given an <code>m x n</code> integers <code>matrix</code>, return <em>the length of the longest increasing path in </em><code>matrix</code>.</p>

<p>From each cell, you can either move in four directions: left, right, up, or down. You <strong>may not</strong> move <strong>diagonally</strong> or move <strong>outside the boundary</strong> (i.e., wrap-around is not allowed).</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/05/grid1.jpg" style="width: 242px; height: 242px;" />
<pre>
<strong>Input:</strong> matrix = [[9,9,4],[6,6,8],[2,1,1]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> The longest increasing path is <code>[1, 2, 6, 9]</code>.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/27/tmp-grid.jpg" style="width: 253px; height: 253px;" />
<pre>
<strong>Input:</strong> matrix = [[3,4,5],[3,2,6],[2,2,1]]
<strong>Output:</strong> 4
<strong>Explanation: </strong>The longest increasing path is <code>[3, 4, 5, 6]</code>. Moving diagonally is not allowed.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> matrix = [[1]]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == matrix.length</code></li>
	<li><code>n == matrix[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 200</code></li>
	<li><code>0 &lt;= matrix[i][j] &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

class Solution {
public:
    vector<pair<int,int>> v[200][200] ;
    vector<pair<int,int>> p[200][200] ;
    void dfs(int i, int j ,vector<vector<int>>&vis,vector<pair<int,int>>&topo ){
        if(vis[i][j])return  ;
        vis[i][j] = 1 ;
        for(pair<int,int> child : v[i][j]){
            dfs(child.first,child.second,vis,topo) ;
        }
        topo.push_back({i,j}) ;
    }
    vector<pair<int,int>>dx = {{-1,0},{1,0},{0,-1},{0,1}} ;
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int n = matrix.size() ;
        int m = matrix[0].size() ;
        for(int i =0;i<n;i++){
            for(int j =0;j<m;j++){
                for(auto &it : dx){
                    int x = i+it.first ;
                    int y = j+it.second ;
                    if(x>=0 && y>=0 && x<n && y<m && matrix[x][y]>matrix[i][j]){
                        v[i][j].push_back({x,y}) ;
                        p[x][y].push_back({i,j}) ;
                    }
                }
            }
        }
        vector<vector<int>>vis(n,vector<int>(m)) ;
        vector<pair<int,int>>topo ;
        for(int i =0;i<n;i++){
            for(int j =0;j<m;j++){
                dfs(i,j,vis,topo) ;
            }
        }
        vector<vector<int>> ans(n,vector<int>(m)) ;
        reverse(topo.begin(),topo.end()) ;
        int tot = 0 ;
        for(pair<int,int> ver : topo){
            int i = ver.first ;
            int j = ver.second ;
            ans[i][j] = 1 ;
            for(pair<int,int> par : p[i][j]){
                int x = par.first ;
                int y = par.second ;
                ans[i][j] = max(ans[i][j],1+ans[x][y]) ;
            }
            tot = max(tot,ans[i][j]) ;
        }
        return tot ;
    }
};
52053