<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:
    // convert the indices for 2d matrices to 1d flat arrays
    pair<int,int> i2d(int rows, int cols, int n){
        return { (int)(n/cols) , (int)(n%cols) };
    }

    int i1d(int rows, int cols, int i, int j){
        return j + i*cols;
    }

    // function to get the neighbours of a given cell
    vector< pair<int,int> > neighbours2d(int rows, int cols, int i, int j){
        vector< pair<int,int> > neighbours;

        // up
        if(i-1 >= 0){
            neighbours.push_back({i-1, j});
        }

        // right
        if(j+1 < cols){
            neighbours.push_back({i, j+1});
        }

        // bottom
        if(i+1 < rows){
            neighbours.push_back({i+1, j});
        }

        // left
        if(j-1 >= 0){
            neighbours.push_back({i, j-1});
        }

        return neighbours;
    }

    int search(int source, vector<int>& flat_vals, vector< vector<int> >& adj, vector<int>& dp){
        if(dp[source] == 0){
            int max_length = 0;

            for(auto n : adj[source]){
                max_length = max(max_length, search(n, flat_vals, adj, dp));
            }

            dp[source] = 1 + max_length;
        }

        return dp[source];
    }

    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();

        int n = rows*cols;

        // adjacency list for all the nodes in the matrix grid
        vector< vector<int> > adj(n, vector<int>(0));

        // flatten the matrix
        vector<int> flat_vals(n, 0);
        for(int i=0 ; i<rows ; i++){
            for(int j=0 ; j<cols ; j++){
                int flat_i = i1d(rows, cols, i, j);

                flat_vals[flat_i] = matrix[i][j];
            }
        }

        for(int i=0 ; i<rows ; i++){
            for(int j=0 ; j<cols ; j++){
                // flat index
                int flat_i = i1d(rows, cols, i, j);

                // get the neighbours of the current cell
                vector< pair<int,int> > neighbours = neighbours2d(rows, cols, i, j);
            
                // add the edges between the nodes
                for(auto n : neighbours){
                    int flat_j = i1d(rows, cols, n.first, n.second);

                    if(flat_vals[flat_i] < flat_vals[flat_j]){
                        adj[flat_i].push_back(flat_j);
                    }
                }
            }
        }

        // cout << "flat: ";
        // for(auto i : flat_vals){
        //     cout << i << ", ";
        // }
        // cout << endl;

        // for(int i=0 ; i<n ; i++){
        //     cout << i << ": ";
        //     for(auto j : adj[i]){
        //         cout << j << ", ";
        //     }
        //     cout << endl;
        // }

        // initialize dp vector
        vector<int> dp(n, 0);
        for(int i=0 ; i<n ; i++){
            if(adj[i].size() == 0){
                dp[i] = 1;
            }
        }

        int max_length = INT_MIN;

        // star the search
        for(int i=0 ; i<n ; i++){
            if(dp[i] == 0){
                search(i, flat_vals, adj, dp);
            }

            max_length = max(max_length, dp[i]);
        }

        return max_length;
    }
};
57703