leetcode 326 矩阵中的最长递增路径

本文主要是介绍leetcode 326 矩阵中的最长递增路径，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

深度优先搜索，思路不难，其中重要的是记忆化搜索，就是搜索的时候记录以当前节点为起点的最长路径的长度。贴代码

 1 class Solution {
 2 public:
 3     int res = 0;
 4     int m;
 5     int n;
 6     int longestIncreasingPath(vector<vector<int>>& matrix) 
 7     {
 8         m = matrix.size();
 9         n = matrix[0].size();
10         vector<vector<int>> memory(m,vector<int>(n,1));
11         int res = 1; 
12         for(int i = 0 ; i < m ; i++)
13         {
14             for(int j = 0 ; j < n ; j++)
15             {
16                 if(memory[i][j] == 1)
17                 {
18                     int temp = dfs(matrix,i,j,memory);
19                     if(temp>res)
20                     res = temp;
21                 }
22             }
23         }
24         return res;
25     }
26     int dfs(vector<vector<int>>& matrix,int i,int j,vector<vector<int>>& memory)
27     {
28         if(memory[i][j]!=1)
29         return memory[i][j];
30         int max = 0;
31         int t1 = 0;
32         int t2 = 0;
33         int t3 = 0;
34         int t4 = 0;
35         if(i+1<m && matrix[i+1][j]>matrix[i][j])
36         t1 = dfs(matrix,i+1,j,memory);
37         if(t1>max)
38         max = t1;
39         if(i-1>=0 && matrix[i-1][j]>matrix[i][j])
40         t2 = dfs(matrix,i-1,j,memory);
41         if(t2>max)
42         max = t2;
43         if(j+1<n && matrix[i][j+1]>matrix[i][j])
44         t3 = dfs(matrix,i,j+1,memory);
45         if(t3>max)
46         max = t3;
47         if(j-1>=0 && matrix[i][j-1]>matrix[i][j])
48         t4 = dfs(matrix,i,j-1,memory);
49         if(t4>max)
50         max = t4;
51         memory[i][j] = max+1;
52         return max+1;
53     }
54 };

这篇关于leetcode 326 矩阵中的最长递增路径的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！