2024蓝桥杯每日一题（DFS）
备战2024年蓝桥杯 -- 每日一题
Python大学A组
试题一：奶牛选美
试题二：树的重心
试题三：大臣的差旅费
试题四：扫雷
试题一：奶牛选美
【题目描述】
听说最近两斑点的奶牛最受欢迎，约翰立即购进了一批两斑点牛。不幸的是，时尚潮流往往变化很快，当前最受欢迎的牛变成了一斑点牛。约翰希望通过给每头奶牛涂色，使得它们身上的两个斑点能够合为一个斑点，让它们能够更加时尚。牛皮可用一个 N×M的字符矩阵来表示，如下所示：
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....其中，X表示斑点部分。如果两个 X在垂直或水平方向上相邻（对角相邻不算在内），则它们属于同一个斑点，由此看出上图中恰好有两个斑点。约翰牛群里所有的牛都有两个斑点。约翰希望通过使用油漆给奶牛尽可能少的区域内涂色，将两个斑点合为一个。在上面的例子中，他只需要给三个 .. 区域内涂色即可（新涂色区域用 ∗ 表示）：
................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
........XXXXX...
.........XXX....请帮助约翰确定，为了使两个斑点合为一个，他需要涂色区域的最少数量。
【输入格式】
第一行包含两个整数 N和 M。
接下来 N 行，每行包含一个长度为 M 的由 X 和 .. 构成的字符串，用来表示描述牛皮图案的字符矩阵。
【输出格式】
输出需要涂色区域的最少数量。
【数据范围】
1≤N,M≤50
【输入样例】
6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....【输出样例】
3【解题思路】
用2次BFS，第一次用来找出两个斑点，第二次用来找最短的连接线。
【Python程序代码】
from collections import *
n,m = map(int,input().split())
a = []
for i in range(n):
a.append(list(input()))
st = [[0]*(m+5) for _ in range(n+5) ]
t,f = 1,0
for i in range(n):
for j in range(m):
if a[i][j]=='X' and st[i][j]==0:
q=deque()
q.append([i,j])
st[i][j]=t
while q:
tx,ty = q.popleft()
for zx,zy in [(-1,0),(1,0),(0,-1),(0,1)]:
nx,ny = tx+zx,ty+zy
if nx<0 or nx>=n or ny<0 or ny>=m:continue
if a[nx][ny]=='.' or st[nx][ny]:continue
st[nx][ny]=t
q.append([nx,ny])
t += 1
def bfs(i_,j_):
q = deque()
q.append([i_,j_,0])
vis = [[0]*(m+5) for _ in range(n+5) ]
vis[i_][j_]=1
while q:
tx,ty,z = q.popleft()
if st[tx][ty]==2:
return z
for zx,zy in [(-1,0),(1,0),(0,1),(0,-1)]:
nx,ny = tx+zx,ty+zy
if nx < 0 or nx >= n or ny < 0 or ny >= m: continue
if vis[nx][ny]: continue
vis[nx][ny]=1
q.append([nx,ny,z+1])
return 0
res = n*m
for i in range(n):
for j in range(m):
if st[i][j]==1:
tep = bfs(i,j)
res = min(res,tep)
print(res-1)
试题二：树的重心
【题目描述】
给定一颗树，树中包含 n个结点（编号 1∼n）和 n−1 条无向边。请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
【输入格式】
第一行包含整数 n，表示树的结点数。
接下来 n−1行，每行包含两个整数 a 和 b，表示点 a 和点 b 之间存在一条边。
【输出格式】
输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。
【数据范围】
1≤n≤100000
【输入样例】
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6【输出样例】
4【解题思路】
本体上就是一个树的遍历问题，遍历去掉每一个点，找出答案。
【Python程序代码】
n = int(input())
h,e,ne,idx = [-1]*(n+5),[0]*(2*n+5),[0]*(2*n+5),0
def add(a,b):
global idx
e[idx]=b; ne[idx]=h[a]; h[a]=idx; idx+=1
for i in range(n-1):
a,b = map(int,input().split())
add(a,b); add(b,a)
ans,st = n,[False]*(n+5)
def dfs(u):
global ans
st[u]=True
res,sumv = 0,1
i = h[u]
while i!=-1:
j = e[i]
if not st[j]:
s = dfs(j)
res = max(res,s)
sumv += s
i = ne[i]
res = max(res,n-sumv)
ans = min(ans,res)
return sumv
dfs(1)
print(ans)
试题三： 大臣的旅费
【题目描述】
很久以前，T王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。为节省经费，T 国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。J 是 T 国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了 J最常做的事情。他有一个钱袋，用于存放往来城市间的路费。聪明的 J发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关。具体来说，一段连续的旅途里，第 1千米的花费为 11，第 2 千米的花费为 12，第 3 千米的花费为 13，…，第 x 千米的花费为 x+10。也就是说，如果一段旅途的总长度为 1 千米，则刚好需要花费 11，如果一段旅途的总长度为 2 千米，则第 1千米花费 11，第 2 千米花费 12，一共需要花费 11+12=23。J 大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？
【输入样例】
【输出格式】
输出一个整数，表示大臣 J 最多花费的路费是多少。
【数据范围】
【输入样例】
5
1 2 2
1 3 1
2 4 5
2 5 4【输出样例】
135【解题思路】
可以发现本题就是求树的直径的问题，经典做法就是先遍历找出距离点d最远的点x，然后找到距离x点最优的y点，其中x到y的距离就是树的直径。
【Python程序代码】
n = int(input())
mp = [[]for i in range(n+1)]
for i in range(n-1):
a,b,c = map(int,input().split())
mp[a].append([b,c])
mp[b].append([a,c])
dist = [0]*(n+1)
def dfs(st,father,distance):
dist[st] = distance
for b,c in mp[st]:
if b!=father:
dfs(b,st,distance+c)
dfs(1,-1,0)
u = 1
for i in range(1,n+1):
if dist[i]>dist[u]:u=i
dfs(u,-1,0)
for i in range(1,n+1):
if dist[i]>dist[u]:u=i
s = dist[u]
print( s*10 + s*(1+s)//2 ) 试题四：扫雷
【题目描述】
小明最近迷上了一款名为《扫雷》的游戏。其中有一个关卡的任务如下：在一个二维平面上放置着 n 个炸雷，第 i个炸雷 (xi,yi,ri)表示在坐标 (xi,yi)(处存在一个炸雷，它的爆炸范围是以半径为 ri 的一个圆。为了顺利通过这片土地，需要玩家进行排雷。玩家可以发射 m 个排雷火箭，小明已经规划好了每个排雷火箭的发射方向，第 j 个排雷火箭 (xj,yj,rj)表示这个排雷火箭将会在 (xj,yj)处爆炸，它的爆炸范围是以半径为 rj 的一个圆，在其爆炸范围内的炸雷会被引爆。同时，当炸雷被引爆时，在其爆炸范围内的炸雷也会被引爆。现在小明想知道他这次共引爆了几颗炸雷？你可以把炸雷和排雷火箭都视为平面上的一个点。一个点处可以存在多个炸雷和排雷火箭。当炸雷位于爆炸范围的边界上时也会被引爆。
【输入格式】
输入的第一行包含两个整数 n、m。
接下来的 n 行，每行三个整数 xi,yi,ri表示一个炸雷的信息。
再接下来的 m 行，每行三个整数 xj,yj,rj表示一个排雷火箭的信息。
【输出格式】
输出一个整数表示答案。
【数据范围】 
【输入样例】
2 1
2 2 4
4 4 2
0 0 5【输出样例】
2【解题思路】
首先，对在同一点的炸雷和排雷火箭进行去重处理，然后枚举每一个排雷火箭，遍历排雷范围，如果能扫到雷则该炸雷也存放到排雷火箭队列。最后用排雷火箭队列模拟排雷。
【Python程序代码】
import sys
from collections import *
input = sys.stdin.readline
n, m = map(int, input().split())
num = Counter()
find = dict()
for _ in range(n):
x, y, r = map(int, input().split())
if (x, y) not in find:
find[(x, y)] = 0
num[(x, y)] += 1
find[(x, y)] = max(find[(x, y)], r)
pq = deque()
f = dict()
for _ in range(m):
x, y, r = map(int, input().split())
if (x, y) not in f:
f[(x, y)] = 0
f[(x, y)] = max(f[(x, y)], r)
for (x, y), r in f.items():
for i in range(x - r, x + r + 1):
for j in range(y - r, y + r + 1):
if (i - x) ** 2 + (j - y) ** 2 <= r ** 2:
if (i, j) in find:
pq.append((i, j, find[(i, j)]))
del find[(i, j)]
res = 0
while pq:
x, y, r = pq.popleft()
res += num[(x, y)]
for i in range(x - r, x + r + 1, 1):
for j in range(y - r, y + r + 1, 1):
if (i - x) ** 2 + (j - y) ** 2 <= r ** 2:
if (i, j) in find:
pq.append((i, j, find[(i, j)]))
del find[(i, j)]
print(res)