2024蓝桥杯每日一题（DFS）_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)
