<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:
    unordered_map<int, int> maxLengthAt;

    int getMaxLength(vector<vector<int>>& matrix, int pos) {
        if (maxLengthAt.find(pos) != maxLengthAt.end()) return maxLengthAt[pos];

        int m = matrix.size(), n = matrix[0].size();
        int i = pos / n, j = pos % n;

        int maxLength = 1;
        
        vector<int> movement;
        if (i > 0) movement.push_back(-n);
        if (i < m - 1) movement.push_back(n);
        if (j > 0) movement.push_back(-1);
        if (j < n - 1) movement.push_back(1);
        
        for (int mv : movement) {
            int newPos = pos + mv;

            if (matrix[newPos / n][newPos % n] > matrix[i][j]) {
                maxLength = max(maxLength, 1 + getMaxLength(matrix, newPos));
            }
                
        }

        maxLengthAt[pos] = maxLength;

        return maxLength;
    }

    int longestIncreasingPath(vector<vector<int>>& matrix) {
        // brute force: traverse all path: mn * 4^(mn)
        // store existing path: (m - 1) * (n - 1) edge, at most O(mn) increasing path
        // so indeed, using increasing edge, the problem is to find longest traverse path in the graph, DFS, we can store existing path by deque (or list), thus, each edge traverse at most once, O(mn)
        int m = matrix.size(), n = matrix[0].size();

        int maxLength = 0;

        for (int i = 0; i < m * n; i++) {
            maxLength = max(maxLength, getMaxLength(matrix, i));
        }

        return maxLength;
    }
};
50640