蓝桥杯---试题算法提高最长滑雪道(bfs)

本文主要是介绍蓝桥杯---试题算法提高最长滑雪道(bfs)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

试题算法提高最长滑雪道

资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
　　小袁非常喜欢滑雪，因为滑雪很刺激。为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。小袁想知道在某个区域中最长的一个滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。如下：
在这里插入图片描述
　　一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上，这是最长的一条。
　　你的任务就是找到最长的一条滑坡，并且将滑坡的长度输出。滑坡的长度定义为经过点的个数，例如滑坡24-17-16-1的长度是4。
输入格式
　　输入的第一行表示区域的行数R和列数C(1<=R, C<=10)。下面是R行，每行有C个整数，依次是每个点的高度h（0<= h <=10000）。
输出格式
　　只有一行，为一个整数，即最长区域的长度。
样例输入
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

思路：
注意样例范围r,c均小于等于10，所以搜索即可；
采用bfs
注意特殊测试点：
当r*c的矩阵每一个点的高度都相同时，此时应该输出1（虽然不能形成所述的滑道但是最小长度为1）
code：

#include<bits/stdc++.h>
using namespace std;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int r,c;
int M[11][11];
int ans=0;
typedef struct Node{int x;int y;int value;
}Node;void bfs(int x,int y)
{Node t;t.x=x;t.y=y;t.value=1;queue<Node> q;q.push(t);while(!q.empty()){Node f=q.front();q.pop();for(int i=0;i<4;i++){int xx=f.x+dir[i][0];int yy=f.y+dir[i][1];if(xx>=1&&xx<=r&&yy>=1&&yy<=c&&M[xx][yy]>M[f.x][f.y]){Node tt;tt.x=xx;tt.y=yy;tt.value=f.value+1;ans=max(ans,tt.value);q.push(tt);}}}
}int main()
{scanf("%d %d",&r,&c);for(int i=1;i<=r;i++){for(int j=1;j<=c;j++){scanf("%d",&M[i][j]);}}for(int i=1;i<=r;i++){for(int j=1;j<=c;j++){bfs(i,j);}}if(ans)printf("%d",ans);else printf("1");return 0;
}