C++刷leetcode(329. 矩阵中的最长递增路径)【深度优先搜索】
本帖最后由 糖逗 于 2020-5-8 18:00 编辑题目描述：
给定一个整数矩阵，找出最长递增路径的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
示例 1:
输入: nums =
[
,
,
]
输出: 4
解释: 最长递增路径为 。
示例 2:
输入: nums =
[
,
,
]
输出: 4
解释: 最长递增路径是 。注意不允许在对角线方向上移动。
来源：力扣（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.size()) return 0;
if(visit > 0) return visit;
int temp = 0;
if(i + 1 < input.size() && input < input){
temp = max(temp, dfs(input, i+1, j, visit));
}
if(i - 1 >= 0 &&input < input){
temp = max(temp, dfs(input, i-1, j, visit));
}
if(j + 1 < input.size() && input < input){
temp = max(temp, dfs(input, i, j+1, visit));
}
if(j - 1 >= 0 && input < input){
temp = max(temp, dfs(input, i, j-1, visit));
}
return visit = temp + 1;
}
int solution(vector<vector<int>>& input) {
int row = input.size();
int col = input.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.size(); j++){
if(visit == 0){
res = max(res, dfs(input, i, j, visit));
}
else{
res = max(res, visit);
}
}
}
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.push_back(number);
}
}
int res = solution(input);
cout << res << endl;
return 0;
}
注意事项：
1.参考代码：https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/solution/javashi-xian-shen-du-you-xian-chao-ji-jian-dan-yi-/
2.动态规划+深度优先搜索思想
3.注意越界的判断if(j - 1 >= 0 && input < input) 注意这四类判断 j-1>=0 要写在 input < input的前面，否则会出现越界。
页:
[1]