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

糖逗

题目描述：

给定一个整数矩阵，找出最长递增路径的长度。

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

示例 1:

输入: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
输出: 4 
解释: 最长递增路径为 [1, 2, 6, 9]。
示例 2:

输入: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
输出: 4 
解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <iostream>
#include <vector>

using namespace std;


int dfs(const vector<vector<int> >& input, int i, int j, vector<vector<int> >& visit){
        if(i < 0 || j < 0 || i >= input.size() || j >= input[0].size()) return 0;
        if(visit[i][j] > 0) return visit[i][j];
        int temp = 0;
        if(i + 1 < input.size() && input[i+1][j] < input[i][j]){
                temp = max(temp, dfs(input, i+1, j, visit));
        }
        if(i - 1 >= 0 &&input[i-1][j] < input[i][j]){
                temp = max(temp, dfs(input, i-1, j, visit));
        }
        if(j + 1 < input[0].size() && input[i][j+1] < input[i][j]){
                temp = max(temp, dfs(input, i, j+1, visit));
        }
        if(j - 1 >= 0 && input[i][j-1] < input[i][j]){
                temp = max(temp, dfs(input, i, j-1, visit));
        }

        return visit[i][j] = temp + 1;
}

int solution(vector<vector<int>>& input) {
        int row = input.size();
        int col = input[0].size();
    if(row == 0)return 0;
    vector<vector<int> > visit(row, vector<int>(col, 0)); 
    int res = 0;
        for(int i = 0; i < input.size(); i++){
                for(int j = 0; j < input[0].size(); j++){
                        if(visit[i][j] == 0){
                                res = max(res, dfs(input, i, j, visit));
                        }
            else{
                res = max(res, visit[i][j]);
            }
                } 
        } 
        return res;
    }



int main(void){
        cout << "send the row for the input vector" << endl; 
        int row;
        cin >> row;
        cin.clear();
        cout << "send the col for the input vector" << endl; 
        int col;
        cin >> col;
        cin.clear();
        vector<vector<int> > input;
        input.resize(row);
        int number; 
        for(int i = 0; i < row; i++){
                for(int j = 0; j < col; j++){
                        cin >> number;
                        input[i].push_back(number);
                } 
        }
        
        int res = solution(input);
        cout << res << endl;
        
        return 0;
} 

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

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

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