解题思路:
1. 首先定义了两个全局变量n和m,分别表示二维数组的行数和列数。
2. 定义了两个二维数组a和b,分别用于存储输入的二维数组和深度优先搜索的结果。
3. 定义了两个一维数组u和v,用于表示上下左右四个方向的偏移量。
4. 定义了一个dfs函数,用于进行深度优先搜索。函数接收三个参数:当前位置的横坐标x、纵坐标y和当前路径长度s。在函数内部,首先将s加1,然后遍历四个方向,如果满足以下条件之一,则跳过当前方向:
- a[x][y]大于等于a[x+u[i]][y+v[i]],表示当前位置的高度小于等于相邻位置的高度,不需要继续搜索了;
- x小于1或大于n,或y小于1或大于m,表示当前位置越界,不需要继续搜索;
- s小于等于b[x+u[i]][y+v[i]],表示当前路径长度小于等于已记录的路径长度,不需要继续搜索。
如果满足搜索条件,则更新b[x+u[i]][y+v[i]]为s,并递归调用dfs函数。
5. 在main函数中,首先读取n和m的值,然后读取二维数组a的数据。接着,遍历二维数组的每个元素,调用dfs函数进行深度优先搜索。最后,遍历二维数组b,找出最大值k,输出k。
注意事项:
参考代码:
#include <iostream>
using namespace std;
int n,m;//输入矩阵大小
int a[1001][1001];//输入矩阵
int b[1001][1001];//存放结果
int u[]={0,0,-1,1},v[]={-1,1,0,0};//控制方向
int dfs(int x,int y,int s)
{
s++;
for(int i=0;i<4;++i)
{//3种不符合的情况
if(a[x][y]<=a[x+u[i]][y+v[i]])
continue;
if(x<1||x>n||y<1||y>m)
continue;
if(s<=b[x+u[i]][y+v[i]])
continue;
b[x+u[i]][y+v[i]]=s;
dfs(x+u[i],y+v[i],s);
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
cin>>a[i][j];
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
dfs(i,j,1);
int k=1;
for(int i=1;i<=n;++i)//找最大值
for(int j=1;j<=m;++j)
if(k<b[i][j])
k=b[i][j];
cout<<k<<endl;
}
0.0分
1 人评分
WU-格式化数据输出 (C++代码)浏览:1212 |
WU-C语言程序设计教程(第三版)课后习题12.1 (C++代码)浏览:940 |
Hello, world! (C++代码)浏览:1744 |
DNA (C语言描述,蓝桥杯)浏览:1555 |
C语言训练-数字母 (C语言代码)浏览:608 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:459 |
简单的a+b (C语言代码)浏览:466 |
C语言训练-斐波纳契数列 (C语言代码)浏览:510 |
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:1325 |
1025题 初学者,求帮忙看下,不知道哪错了浏览:316 |