leetcode - 329. 矩阵中的最长递增路径

题目

代码

#include <iostream>
#include <vector>
using namespace std;

/* 转换思路，将其看作图，当相邻的两个数不等时，就会存在一条由大值指向小值的边 那我们要找的就是图的最长路径，所以用dfs */
int m, n;
int dir[4][2] = {
    {
    -1, 0}, {
    1, 0}, {
    0, -1}, {
    0, 1}};

int dfs(vector<vector<int> >& matrix, vector<vector<int> >& memo, int i, int j){
    
	if(memo[i][j] != 0){
    
		return memo[i][j];
	}
	memo[i][j]++;
	for(int k = 0; k < 4; k++){
    
		int x = i + dir[k][0];
		int y = j + dir[k][1];
		if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]){
    
			memo[i][j] = max(memo[i][j], dfs(matrix, memo, x, y) + 1);
		}
	}
	return memo[i][j];
}
 
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 = 1;
	vector<vector<int> > memo(m, vector<int>(n, 0));
	for(int i = 0; i < m; i++){
    
		for(int j = 0; j < n; j++){
    
			res = max(res, dfs(matrix, memo, i, j));
		}
	}
	return res;
}

int main(){
    
	int m, n, res;
	cin>>m>>n;
	vector<vector<int> > matrix(m, vector<int>(n));
	for(int i = 0; i < m; i++){
    
		for(int j = 0; j < n; j++){
    
			cin>>matrix[i][j];
		}
	}
	res = longestIncreasingPath(matrix);
	cout<<res;
    return 0;
}