C++刷leetcode(329. 矩阵中的最长递增路径)【深度优先搜索】

糖逗

题目描述：

1. 给定一个整数矩阵，找出最长递增路径的长度。
   
2. 
   
3. 对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
   
4. 
   
5. 示例 1:
   
6. 
   
7. 输入: nums =
   
8. [
   
9.   [9,9,4],
   
10.   [6,6,8],
    
11.   [2,1,1]
    
12. ]
    
13. 输出: 4
    
14. 解释: 最长递增路径为 [1, 2, 6, 9]。
    
15. 示例 2:
    
16. 
    
17. 输入: nums =
    
18. [
    
19.   [3,4,5],
    
20.   [3,2,6],
    
21.   [2,2,1]
    
22. ]
    
23. 输出: 4
    
24. 解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
    
25. 
    
26. 来源：力扣（LeetCode）
    
27. 链接：https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix
    
28. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. using namespace std;
   
5. 
   
6. 
   
7. int dfs(const vector<vector<int> >& input, int i, int j, vector<vector<int> >& visit){
   
8.         if(i < 0 || j < 0 || i >= input.size() || j >= input[0].size()) return 0;
   
9.         if(visit[i][j] > 0) return visit[i][j];
   
10.         int temp = 0;
    
11.         if(i + 1 < input.size() && input[i+1][j] < input[i][j]){
    
12.                 temp = max(temp, dfs(input, i+1, j, visit));
    
13.         }
    
14.         if(i - 1 >= 0 &&input[i-1][j] < input[i][j]){
    
15.                 temp = max(temp, dfs(input, i-1, j, visit));
    
16.         }
    
17.         if(j + 1 < input[0].size() && input[i][j+1] < input[i][j]){
    
18.                 temp = max(temp, dfs(input, i, j+1, visit));
    
19.         }
    
20.         if(j - 1 >= 0 && input[i][j-1] < input[i][j]){
    
21.                 temp = max(temp, dfs(input, i, j-1, visit));
    
22.         }
    
23. 
    
24.         return visit[i][j] = temp + 1;
    
25. }
    
26. 
    
27. int solution(vector<vector<int>>& input) {
    
28.         int row = input.size();
    
29.         int col = input[0].size();
    
30.     if(row == 0)return 0;
    
31.     vector<vector<int> > visit(row, vector<int>(col, 0));
    
32.     int res = 0;
    
33.         for(int i = 0; i < input.size(); i++){
    
34.                 for(int j = 0; j < input[0].size(); j++){
    
35.                         if(visit[i][j] == 0){
    
36.                                 res = max(res, dfs(input, i, j, visit));
    
37.                         }
    
38.             else{
    
39.                 res = max(res, visit[i][j]);
    
40.             }
    
41.                 }
    
42.         }
    
43.         return res;
    
44.     }
    
45. 
    
46. 
    
47. 
    
48. int main(void){
    
49.         cout << "send the row for the input vector" << endl;
    
50.         int row;
    
51.         cin >> row;
    
52.         cin.clear();
    
53.         cout << "send the col for the input vector" << endl;
    
54.         int col;
    
55.         cin >> col;
    
56.         cin.clear();
    
57.         vector<vector<int> > input;
    
58.         input.resize(row);
    
59.         int number;
    
60.         for(int i = 0; i < row; i++){
    
61.                 for(int j = 0; j < col; j++){
    
62.                         cin >> number;
    
63.                         input[i].push_back(number);
    
64.                 }
    
65.         }
    
66.        
    
67.         int res = solution(input);
    
68.         cout << res << endl;
    
69.        
    
70.         return 0;
    
71. }

复制代码

注意事项：
1.参考代码：https://leetcode-cn.com/problems ... ao-ji-jian-dan-yi-/
2.动态规划+深度优先搜索思想
3.注意越界的判断

1. if(j - 1 >= 0 && input[i][j-1] < input[i][j])

复制代码

  注意这四类判断 j-1>=0 要写在 input[j-1] < input[j]的前面，否则会出现越界。