BM61. 矩阵最长递增路径
描述
示例1
输入:
[[1,2,3],[4,5,6],[7,8,9]]
输出:
5
说明:
1->2->3->6->9即可。当然这种递增路径不是唯一的。示例2
输入:
[[1,2],[4,3]]
输出:
4
说明:
1->2->3->4C++ 解法, 执行用时: 92ms, 内存消耗: 14056KB, 提交时间: 2022-08-02
const auto io_sync_off=[]() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return nullptr;
}();
typedef vector<vector<int>> Matrix;
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 递增路径的最大长度
* @param matrix int整型vector<vector<>> 描述矩阵的每个数
* @return int整型
*/
int solve(vector<vector<int> >& matrix) {
// write code here
vector<vector<int>> cache(matrix.size(), vector<int>(matrix[0].size(), 0));
int ans = 0;
for (int i = 0; i < matrix.size(); i++)
for (int j = 0; j < matrix[0].size(); j++)
ans = max(ans, dfs(matrix, cache, i, j));
return ans;
}
private:
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int dfs(Matrix& matrix, Matrix& cache, int x, int y) {
if (cache[x][y] > 0)
return cache[x][y];
int cur = 1;
for (int i = 0; i < 4; i++) {
int nx = x + directions[i][0];
int ny = y + directions[i][1];
if (nx < 0 || nx >= matrix.size())
continue;
if (ny < 0 || ny >= matrix[0].size())
continue;
if (matrix[x][y] >= matrix[nx][ny])
continue;
cur = max(cur, dfs(matrix, cache, nx, ny) + 1);
}
cache[x][y] = cur;
return cur;
}
};
C++ 解法, 执行用时: 97ms, 内存消耗: 14120KB, 提交时间: 2022-06-18
const auto io_sync_off=[]() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return nullptr;
}();
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 递增路径的最大长度
* @param matrix int整型vector<vector<>> 描述矩阵的每个数
* @return int整型
*/
int step[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int solve(vector<vector<int> >& matrix) {
// write code here
if (matrix.size() < 1) {
return 0;
}
int res = 0;
int m = matrix.size();
int n = matrix[0].size();
vector<vector<int>> dp(m, vector<int>(n));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
res = max(res, DFS(matrix,dp,i,j));
}
}
return res;
}
int DFS(vector<vector<int>>& matrix, vector<vector<int>>& dp, int x, int y) {
if (dp[x][y] != 0) {
return dp[x][y];
}
dp[x][y] += 1;
int m = matrix.size();
int n = matrix[0].size();
for (int i = 0; i < 4; i++) {
int nx = x + step[i][0];
int ny = y + step[i][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[x][y] < matrix[nx][ny]) {
dp[x][y] = max(dp[x][y], DFS(matrix,dp,nx,ny) + 1);
}
}
return dp[x][y];
}
};
C++ 解法, 执行用时: 108ms, 内存消耗: 14088KB, 提交时间: 2021-12-06
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 递增路径的最大长度
* @param matrix int整型vector<vector<>> 描述矩阵的每个数
* @return int整型
*/
int dfs(vector<vector<int>> &m, int x, int y, vector<vector<int>> &rec) {
if (rec[x][y] != 0)
return rec[x][y];
int len = 1;
if (x > 0 && m[x - 1][y] > m[x][y])
len = max(len, 1 + dfs(m, x - 1, y, rec));
if (y > 0 && m[x][y - 1] > m[x][y])
len = max(len, 1 + dfs(m, x, y - 1, rec));
if (x + 1 < m.size() && m[x + 1][y] > m[x][y])
len = max(len, 1 + dfs(m, x + 1, y, rec));
if (y + 1 < m[0].size() && m[x][y + 1] > m[x][y])
len = max(len, 1 + dfs(m, x, y + 1, rec));
rec[x][y] = len;
return len;
}
int solve(vector<vector<int> >& matrix) {
// write code here
vector<vector<int>> rec(matrix.size(), vector<int>(matrix[0].size(), 0));
int len = 0;
for (int i = 0; i < matrix.size(); i++) {
for (int j = 0; j < matrix[0].size(); j++) {
len = max(len, dfs(matrix, i, j, rec));
}
}
return len;
}
};
C++ 解法, 执行用时: 109ms, 内存消耗: 14032KB, 提交时间: 2022-05-12
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
/* 递归dfs
主函数
1.防御性编程
2.定义cnt最大值max，当前元素最长递增路径dp
3.遍历元素每个调用子函数dfs:cnt传引用值
4.返回
子函数
1.判断出口条件：ij位置dp不为0,
2.上下左右哪个位置大，dfs哪个位置，更新dp值
*/
int solve(vector<vector<int> >& matrix) {
if(matrix.empty() || matrix[0].empty()) return 0;
n=matrix.size();
m=matrix[0].size();
int res=0;
// 以当前元素为起点的最长路径长度
vector<vector<int>> dp(n,vector<int>(m));
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
res=max(res,dfs(matrix,dp,i,j));
}
}
return res;
}
int dfs(vector<vector<int>> &matrix,vector<vector<int>> &dp,int i,int j){
if(dp[i][j]!=0) return dp[i][j];
dp[i][j]++;
/*
for(int k=0; k<4; k++) {
int nexti=i+dir[k][0];
int nextj=j+dir[k][1];
if(nexti>=0 && nexti<n && nextj>=0 && nextj<m && matrix[i][j]<matrix[nexti][nextj])
dp[i][j]=max(dp[i][j],dfs(matrix,dp,nexti,nextj)+1);
}*/
if(i-1>=0 && i-1<n && j>=0 && j<m && matrix[i-1][j]>matrix[i][j])
dp[i][j]=max(dp[i][j],dfs(matrix,dp,i-1,j)+1);
if(i+1>=0 && i+1<n && j>=0 && j<m && matrix[i+1][j]>matrix[i][j])
dp[i][j]=max(dp[i][j],dfs(matrix,dp,i+1,j)+1);
if(i>=0 && i<n && j-1>=0 && j-1<m && matrix[i][j-1]>matrix[i][j])
dp[i][j]=max(dp[i][j],dfs(matrix,dp,i,j-1)+1);
if(i>=0 && i<n && j+1>=0 && j+1<m && matrix[i][j+1]>matrix[i][j])
dp[i][j]=max(dp[i][j],dfs(matrix,dp,i,j+1)+1);
return dp[i][j];
}
int max(int a,int b) {
return a>b?a:b;
}
private:
int n,m;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
};
C++ 解法, 执行用时: 109ms, 内存消耗: 16924KB, 提交时间: 2021-08-18
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 递增路径的最大长度
* @param matrix int整型vector<vector<>> 描述矩阵的每个数
* @return int整型
*/
int solve(vector<vector<int> >& matrix) {
// write code here
if(matrix.size() == 0 || matrix[0].size() == 0)
return 0;
int m = matrix.size();
int n = matrix[0].size();
int res = 0;
vector<vector<int>> dp(m,vector<int>(n,0));
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
res = max(res,dfs(matrix,i,j,dp));
}
}
return res;
}
int dfs(vector<vector<int>> &matrix,int i,int j,vector<vector<int>> &dp){
if(dp[i][j] != 0)
return dp[i][j];
int l = 0,r = 0, u = 0,d = 0;
if(j-1 >= 0 && matrix[i][j-1] > matrix[i][j]){
if(dp[i][j-1] != 0)
l = dp[i][j-1];
else
l = dfs(matrix,i,j-1,dp);
}
if(j+1 < matrix[0].size() && matrix[i][j+1] > matrix[i][j]){
if(dp[i][j+1] != 0)
r = dp[i][j+1];
else
r = dfs(matrix,i,j+1,dp);
}
if(i-1 >= 0 && matrix[i-1][j] > matrix[i][j]){
if(dp[i-1][j] != 0)
u = dp[i-1][j];
else
u = dfs(matrix,i-1,j,dp);
}
if(i+1 < matrix.size() && matrix[i+1][j] > matrix[i][j]){
if(dp[i+1][j] != 0)
d = dp[i+1][j];
else
d = dfs(matrix,i+1,j,dp);
}
int k = max(max(max(l,r),u),d)+1;
dp[i][j] = k;
return k;
}
};