# 矩阵中的最长递增路径

<p>给定一个 <code>m x n</code> 整数矩阵 <code>matrix</code> ，找出其中 <strong>最长递增路径</strong> 的长度。</p>

<p>对于每个单元格，你可以往上，下，左，右四个方向移动。 你 <strong>不能</strong> 在 <strong>对角线</strong> 方向上移动或移动到 <strong>边界外</strong>（即不允许环绕）。</p>

<p> </p>

<p><strong>示例 1：</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/05/grid1.jpg" style="width: 242px; height: 242px;" />
<pre>
<strong>输入：</strong>matrix = [[9,9,4],[6,6,8],[2,1,1]]
<strong>输出：</strong>4 
<strong>解释：</strong>最长递增路径为 <code>[1, 2, 6, 9]</code>。</pre>

<p><strong>示例 2：</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/27/tmp-grid.jpg" style="width: 253px; height: 253px;" />
<pre>
<strong>输入：</strong>matrix = [[3,4,5],[3,2,6],[2,2,1]]
<strong>输出：</strong>4 
<strong>解释：</strong>最长递增路径是 <code>[3, 4, 5, 6]</code>。注意不允许在对角线方向上移动。
</pre>

<p><strong>示例 3：</strong></p>

<pre>
<strong>输入：</strong>matrix = [[1]]
<strong>输出：</strong>1
</pre>

<p> </p>

<p><strong>提示：</strong></p>

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


## template

```cpp
#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int m, n;
    int longestIncreasingPath(vector<vector<int>> &matrix)
    {
        if (matrix.size() == 0 || matrix[0].size() == 0)
        {
            return 0;
        }
        m = matrix.size();
        n = matrix[0].size();
        int res = 0;
        auto memo = vector<vector<int>>(m, vector<int>(n, 0));
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (memo[i][j])
                    res = max(res, memo[i][j]);
                else
                    res = max(res, dfs(i, j, matrix, memo));
            }
        }
        return res;
    }

    int dfs(int i, int j, vector<vector<int>> &matrix, vector<vector<int>> &memo)
    {
        int temp = 1;
        for (int k = 0; k < 4; ++k)
        {
            int x = i + dirs[k][0];
            int y = j + dirs[k][1];
            if ((x >= 0) && (x < m) && (y >= 0) && (y < n) && (matrix[i][j] < matrix[x][y]))
            {
                if (memo[x][y])
                    temp = max(temp, memo[x][y] + 1);
                else
                    temp = max(temp, dfs(x, y, matrix, memo) + 1);
            }
        }
        memo[i][j] = temp;
        return temp;
    }
};


```

## 答案

```cpp

```

## 选项

### A

```cpp

```

### B

```cpp

```

### C

```cpp

```