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)