作者🕵️‍♂️：让机器理解语言か

专栏🎇：蓝桥杯倒计时冲刺

描述🎨：蓝桥杯冲刺阶段，一定要沉住气，一步一个脚印，胜利就在前方！

寄语💓：🐾没有白走的路，每一步都算数！🐾

题目1：信号覆盖 

信号覆盖 - 蓝桥云课 (lanqiao.cn)

问题描述

小蓝负责一块区域的信号塔安装，整块区域是一个长方形区域，建立坐标轴后，西南角坐标为 (0,0)， 东南角坐标为 (W,0)， 西北角坐标为 (0,H)， 东北角坐标为 (W,H)。其中 W, H 都是整数。他在 n 个位置设置了信号塔，每个信号塔可以覆盖以自己为圆心，半径为 R 的圆形（包括边缘）。为了对信号覆盖的情况进行检查，小蓝打算在区域内的所有横纵坐标为整数的点进行测试，检查信号状态。其中横坐标范围为 0 到 W，纵坐标范围为 00 到 H，总共测试(W+1)×(H+1) 个点。

给定信号塔的位置，请问这 (W+1)×(H+1) 个点中有多少个点被信号覆盖。

输入格式

输入第一行包含四个整数 W,H,n,R，相邻整数之间使用一个空格分隔。

接下来 n 行，每行包含两个整数 x,y，表示一个信号塔的坐标。信号塔可能重合，表示两个信号发射器装在了同一个位置。

输出格式

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

样例输入

10 10 2 5
0 0
7 0

样例输出

57

 评测用例规模与约定

对于所有评测用例，1≤W,H≤100，1≤n≤100,1≤R≤100,0≤x≤W,0≤y≤H。

思路： 

1、怎么确定一点在区域的范围内？

为了减小遍历区间范围，所以首先确定该信号塔范围的边界，只在信号塔所在圆的外切正方形内搜索：

左右边界：        x1, x2 = x-r,  x+r 
上下边界：        y1, y2 = y-r, y+r

再用两层循环遍历左右边界和上下边界，如果x<0或x>w，y<0或y>h说明该点不在范围内。

2、怎么统计信号塔范围内点的数量？

首先判断该点是否在圆内：abs(i1-x)*abs(i1-x) + abs(j1-y)*abs(j1-y) <= r*r（负数不能相乘，先用abs()取绝对值）

若在圆内则添加到集合l，对于两个信号塔范围重叠部分的坐标，集合会自动去重，最后取出集合l的长度就是信号塔范围内的点数 

代码： 

l = set(())    # 去掉重复的点
w,h,n,r = map(int,input().split())
for i in range(n):x,y = map(int,input().split())x1, x2 = x-r, x+r  # 遍历左右坐标y1, y2 = y-r, y+r  # 遍历上下坐标for i1 in range(x1,x2+1): # 将坐标对应的区域遍历if i1 <0 or i1 > w:   # 判断超过区域的数直接跳过continuefor j1 in range(y1,y2+1):if j1 < 0 or j1 > h: #判断超过区域的数直接跳过continueif abs(i1-x)*abs(i1-x) + abs(j1-y)*abs(j1-y) <= r*r: # 判断点到圆点的距离l.add((i1,j1)) # 满足就添加到集合里面自动去重了
print(len(l))

题目2：滑行 

滑行 - 蓝桥云课 (lanqiao.cn)

问题描述

小蓝准备在一个空旷的场地里面滑行，这个场地的高度不一，小蓝用一个 n 行 m 列的矩阵来表示场地，矩阵中的数值表示场地的高度。如果小蓝在某个位置，而他上、下、左、右中有一个位置的高度（严格）低于当前的高度，小蓝就可以滑过去，滑动距离为 1 。如果小蓝在某个位置，而他上、下、左、右中所有位置的高度都大于等于当前的高度，小蓝的滑行就结束了。小蓝不能滑出矩阵所表示的场地。小蓝可以任意选择一个位置开始滑行，请问小蓝最多能滑行多远距离。

输入格式

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

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

输出格式

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

样例输入

4 5
1 4 6 3 1 
11 8 7 3 1 
9 4 5 2 1 
1 3 2 2 1

样例输出

7

样例说明

滑行的位置一次为 (2,1),(2,2),(2,3),(3,3),(3,2),(4,2),(4,3)(2,1),(2,2),(2,3),(3,3),(3,2),(4,2),(4,3)。

评测用例规模与约定

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

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

思路： 

一道简单的搜索题，用深度优先搜索（DFS）来写 

小蓝可以从任意一点出发，所以从地图上每一点 开始搜索，用两层循环遍历每一点。

DFS过程就是搜索当前位置所能达到的最远距离

• 记忆化：jiyi( )记录了当前位置所能达到的最远距离，后面再遇到就不再运算重复路线，直接返回当前位置所能达到的最远距离。
• 遍历当前位置的四个方向，求出下一点的坐标；如果下一点在界内且下一点比当前点更低，则取出四个方向的点中可以达到的最远距离。四个方向的点中可以达到的最远距离+1就是当前点可以到达的最远距离。用列表jiyi( )进行记录当前点可以到达的最远距离（记忆化）。

代码：

n, m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(n)] # 二维列表保存地图高度
jiyi = [[-1] * m for _ in range(n)]  # 记忆化搜索
# 记忆化搜索: -1代表没记录当前位置所能达到的最远距离，其他值代表已经记录了当前位置所能达到的最远距离def dfs(x, y):  # 搜索当前位置所能达到的最远距离if jiyi[x][y] != -1:   # 如果被记录过了return jiyi[x][y]  # 直接返回当前位置所能达到的最远距离ans = 1for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]: # 当前位置的四个方向xx = dx + xyy = dy + yif 0 <= xx < n and 0 <= yy < m and lst[xx][yy] < lst[x][y]: # 在界内且下一个位置比当前位置低ans = max(dfs(xx, yy) + 1, ans)  # dfs(xx, yy) + 1：(x, y)达到最远的距离=(xx, yy)达到最远的距离 + 1jiyi[x][y] = ans  # 每次走到尽头了就记录一下当前这条路线走了几步（距离）return ans  # 返回当前位置所能达到的最远距离res = 0
# 可以从任意一个点出发，所以遍历地图所有点
for i in range(n):for j in range(m):res = max(dfs(i, j), res) # 所有位置所能达到的最远距离print(res)