<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 {
vector<bool> visited;
vector<int> most;
vector<vector<int>> adj;

int visit(int index)
{
    cout<<"visit "<<index<<endl;
    if (visited[index]) return most[index];
    visited[index]=true;
    for (int i : adj[index])
    {
        most[index]=max(most[index], visit(i)+1);
    }
    return most[index];
}
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int n=matrix.size(), m=matrix[0].size();
    int tot=n*m; // the size of the aays
    
    vector<vector<int>> nums=matrix;
    // the geatest length fo values above only that can be eached fom a given po
    for (int i=0;i<tot;i++)
    {
        most.push_back(1);
        visited.push_back(false);
        adj.push_back({});
    }
    priority_queue<vector<int>> lowest; // fist is the values, second is the indices of the lowest values, to be checked
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<m;j++)
        {
            int val=nums[i][j];
            if (i>0 && nums[i-1][j]>val) adj[i*m+j].push_back((i-1)*m+j);
            if (i<n-1 && nums[i+1][j]>val) adj[i*m+j].push_back((i+1)*m+j);
            if (j>0 && nums[i][j-1]>val) adj[i*m+j].push_back(i*m+j-1);
            if (j<m-1 && nums[i][j+1]>val) adj[i*m+j].push_back(i*m+j+1);
            lowest.push({-val,i*m+j});
        }
    }

    int best=0; // the longest length seen so fa
    while (lowest.size()>0)
    {
        cout<<"still emoving "<<lowest.size()<<endl;
        int index=lowest.top()[1];
        if (!visited[index]) best=max(best,visit(index));
        lowest.pop();
    }
    return best;
    }
};
60528