(dfs)(枚举)第十四届蓝桥杯第三次模拟赛:9.最大滑雪长度

简介: (dfs)(枚举)第十四届蓝桥杯第三次模拟赛:9.最大滑雪长度

题目链接

题目来源:第十四届蓝桥杯第三期模拟赛

题目难度:简单


题目描述:小蓝准备在一个空旷的场地里面滑行,这个场地的高度不一,小蓝用一个 n 行 m 列的矩阵来表示场地,矩阵中的数值表示场地的高度。

 如果小蓝在某个位置,而他上、下、左、右中有一个位置的高度(严格)低于当前的高度,小蓝就可以滑过去,滑动距离为 1 。

 如果小蓝在某个位置,而他上、下、左、右中所有位置的高度都大于等于当前的高度,小蓝的滑行就结束了。

 小蓝不能滑出矩阵所表示的场地。

 小蓝可以任意选择一个位置开始滑行,请问小蓝最多能滑行多远距离。


输入第一行包含两个整数 n, m,用一个空格分隔。

接下来 n 行,每行包含 m 个整数,相邻整数之间用一个空格分隔,依次表示每个位置的高度。


输出一行包含一个整数,表示答案。


对于 30% 评测用例,1 <= n <= 20,1 <= m <= 20,0 <= 高度 <= 100。

对于所有评测用例,1 <= n <= 100,1 <= m <= 100,0 <= 高度 <= 10000。

一些话


切入点

如果小蓝在某个位置,而他上、下、左、右中有一个位置的高度(严格)低于当前的高度,小蓝就可以滑过去,滑动距离为 1 。

 如果小蓝在某个位置,而他上、下、左、右中所有位置的高度都大于等于当前的高度,小蓝的滑行就结束了。


小蓝可以往上下左右满足条件的地方移动,符合dfs和bfs的特征


流程

小蓝可以任意选择一个位置开始滑行,请问小蓝最多能滑行多远距离

先枚举小蓝开始滑雪的位置,如果小蓝在某个位置,而他上、下、左、右中有一个位置的高度(严格)低于当前的高度,小蓝就可以滑过去,滑动距离为 1 。

再在dfs内枚举小蓝往上下左右移动后的坐标,如果满足条件就继续递归,

因为小蓝只能从高处滑向低处,所以不需要bool数组来记录小蓝滑过哪些地方

如果小蓝在某个位置,而他上、下、左、右中所有位置的高度都大于等于当前的高度,小蓝的滑行就结束了。

由此可以得到递归的结束条件是小蓝上下左右都不可以滑


套路

坐标移动的枚举

int dx[] = {0,0,1,-1},dy[] = {1,-1,0,0};
for(int i = 0;i < 4;i++){
    int a = x + dx[i];
    int b = y + dy[i];
}

ac代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};
bool st[100][100];
int  map[100][100];
int res = 0,cnt;
int n,m;
void bfs(int x,int y){    
    for(int i = 0;i < 4;i++){
        int a = x + dx[i];
        int b = y + dy[i];
        if(a >= 0 && a < n && b >= 0 && b < m && map[a][b] < map[x][y]){
            cnt++;
            st[a][b] = true;
            res = max(res,cnt);
            bfs(a,b);
            st[a][b] = false;
        }
    }
}
int main(){
    cin>> n >> m;
    // cout << n << m;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cin >> map[i][j];
            // cout << i << " " << j << ' ';
            // cout << map[i][j];
        }
        // cout << endl;
    }
    // cout << cnt;
    int t = 0;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            bfs(i,j);
            int n = 0;
        }
    }    
    cout << res << endl;
    return 0;
}
目录
打赏
0
0
0
0
0
分享
相关文章
|
10月前
|
第十四届蓝桥杯集训——JavaC组第十二篇——while循环(循环四要素)
第十四届蓝桥杯集训——JavaC组第十二篇——while循环(循环四要素)
100 0
PTA 浙大版《C语言程序设计(第3版)》题目集 习题8-6 删除字符 (20分)
PTA 浙大版《C语言程序设计(第3版)》题目集 习题8-6 删除字符 (20分)
|
10月前
|
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-试题 基础练习 十六进制转八进制
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-试题 基础练习 十六进制转八进制
63 0
|
10月前
|
C++
蓝桥杯15届第二次模拟C++
蓝桥杯15届第二次模拟C++
56 0
蓝桥杯15届第二次模拟赛C/C++详解
蓝桥杯15届第二次模拟赛C/C++详解
194 0
02【C语言 & 趣味算法】借书方案问题:小明有5本新书,要借给A、B、C三位小朋友,若每人每次只能借1本,则可以有多少种不同的借法?
02【C语言 & 趣味算法】借书方案问题:小明有5本新书,要借给A、B、C三位小朋友,若每人每次只能借1本,则可以有多少种不同的借法?
02【C语言 & 趣味算法】借书方案问题:小明有5本新书,要借给A、B、C三位小朋友,若每人每次只能借1本,则可以有多少种不同的借法?
【每日一题Day95】LC1815得到新鲜甜甜圈的最多组数 | 状态压缩dp 记忆化搜索
子问题、哪些操作会影响数据:余下的甜甜圈数量left,以及剩余可以选的元素个数 cnt[x]【dfs函数的两个参数->使用状态压缩至一个int类型变量中】
129 0
【每日一题Day95】LC1815得到新鲜甜甜圈的最多组数 | 状态压缩dp 记忆化搜索
【蓝桥杯集训·每日一题】AcWing 3956. 截断数组
文章目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 三、知识风暴 一维前缀和
77 0
【蓝桥杯集训·每日一题】AcWing 3502. 不同路径数
文章目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 三、知识风暴
108 0
第十四届蓝桥杯第三次模拟赛:6 求星期几
第十四届蓝桥杯第三次模拟赛:6 求星期几
113 0