求点赞
2025-07-05 15:20:31
发布于:广东
4阅读
0回复
0点赞
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 定义二维数组的行和列的最大值
const int MAX_R = 100;
const int MAX_C = 100;
// 定义上、下、左、右四个方向的坐标变化
const int dx[4] { -1, 1, 0, 0 };
const int dy[4] { 0, 0, -1, 1 };
int R, C; // 行数和列数
int arr[MAX_R][MAX_C]; // 存储二维数组的值
int dp[MAX_R][MAX_C]; // 存储以每个位置为起点的最长下降路径长度
int dfs(int x, int y) {
if (dp[x][y] > 0) {
return dp[x][y];
}
int max_length = 1;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < R && ny >= 0 && ny < C && arr[nx][ny] < arr[x][y]) {
int length = 1 + dfs(nx, ny);
max_length = max(max_length, length);
}
}
dp[x][y] = max_length;
return max_length;
}
int findLongestPath() {
int max_length = 0;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
int length = dfs(i, j);
max_length = max(max_length, length);
}
}
return max_length;
}
int main() {
cin >> R >> C;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cin >> arr[i][j];
}
}
int result = findLongestPath();
cout << result << endl;
return 0;
}
全部评论 1
#include<bits/stdc++.h>
using namespace std;
int n, m, ans;
int maps[105][105];
int dir[4][2]={0,1,1,0,-1,0,0,-1};
int f[105][105];
int dfs(int x,int y){
if(f[x][y]){
return f[x][y];
}
int len=1;
for(int i=0; i<4; i++){
int a=x+dir[i][0];
int b=y+dir[i][1];
if(maps[a][b]<maps[x][y] && maps[a][b]!=-1){
len=max(len,dfs(a,b)+1);
}
}
f[x][y]=len;
return f[x][y];
}int main(){
memset(maps,-1,sizeof(maps));
cin>>n>>m;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cin>>maps[i][j];
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
ans=max(ans,dfs(i,j));
}
}
cout<<ans;
return 0;
}1周前 来自 天津
0
有帮助,赞一个