算法——矩阵最长滑翔路径
算法描述
【问题描述】
在一个C行R列的矩阵M中，其元素M[i][j]可以滑翔到相邻的上下左右的四个元素中的一个(当然不能超出矩阵的边界)，当且仅当相邻的元素比它要小，因为只能从高处滑翔到低处，每滑翔到一个元素，路径长度加1，现在要求你编程计算该矩阵中最长的滑翔路径长度是多少。
要求输入矩阵的行列数和各元素的值，计算输出该矩阵中最长的滑翔路径长度。并给出路径。
【输入样例】
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
【输出样例】
25
25 24……1
C语言实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include<stdio.h>
#include<string.h>
int G[100][100],len[100][100],have[100][100];
int n,m,mov[2][4]={0,0,1,-1,1,-1,0,0};
bool bound(int p,int q)
{
return p>n||p<1||q>m||q<1;
}
int DFS(int p,int q)
{
if(have[p][q])
return len[p][q];
int ans=1;
for(int i=0;i<4;i++)
{
int np=p+mov[0][i],nq=q+mov[1][i];
if(bound(np,nq)) continue;
if(G[p][q]>G[np][nq]){
if(ans>DFS(np,nq)+1)
ans=ans;
else
{
ans=DFS(np,nq)+1;
}
}
}
len[p][q]=ans;
have[p][q]=1;
return ans;
}
int main(){
int i,j,maxi,maxj;
printf("请输入行列数(用空格分隔):\n");
scanf("%d %d",&n,&m);
G[0][0]=0;
printf("请输入矩阵的值:\n");
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
scanf("%d",&G[i][j]);
have[i][j]=0;
}
int ans=0;
for(i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
len[i][j]=DFS(i,j);
if(ans>len[i][j])
ans=ans;
else
{
ans=len[i][j];
maxi=i;
maxj=j;
}
}
printf("最长滑翔长度是%d\n",ans);
for(i=ans;i>1;i--)
printf("%d-",i);
printf("1");
return 0;
}
|
运行截图
