【华为机试】2023年真题B卷（python）-发广播

一、题目

题目描述：

某地有N个广播站，站点之间有些有连接，有些没有。有连接的站点在接受到广播后会互相发送。
给定一个N*N的二维数组matrix,数组的元素都是字符’0’或者’1’。
matrix[i][j]=‘1’,则代表i和j站点之间有连接，matrix[i][j]=‘0’代表没连接，现在要发一条广播，问初始最少给几个广播站发送，才能保证所有的广播站都收到消息。

二、输入输出

输入描述：
从stdin输入，共一行数据，表示二维数组的各行，用逗号分隔行。保证每行字符串所含的字符数一样的。
比如：110,110,001。
输出描述：
返回初始最少需要发送广播站个数。

三、示例

示例1???
输入输出示例仅供调试，后台判题数据一般不包含示例
输入：
110,110,001
输出：
2
说明：
站点1和站点2直接有连接，站点3和其他的都没连接，所以开始至少需要给两个站点发送广播。

四、解题思路

1. 首先，我们可以使用深度优先搜索（DFS）来遍历广播站的连接情况。
2. 对于每个广播站，我们可以从该站开始进行DFS遍历，将与该站直接或间接相连的所有站点标记为已访问。
3. 在遍历过程中，我们可以使用一个集合visited来记录已访问的站点。
4. 最终，遍历完成后，集合visited中的元素个数即为初始最少需要发送广播站的个数。

五、参考代码?

# -*- coding: utf-8 -*-
'''
@File    :   2023-B-发广播.py
@Time    :   2023/12/24 23:33:17
@Author  :   mgc 
@Version :   1.0
@Desc    :   None
'''

# import os
# import re
# import sys
# import copy
# import math
# import queue
# import functools
# from queue import Queue
# from collections import Counter, defaultdict

def min_stations(matrix):
    n = len(matrix)
    visited = set()  # 用于记录已访问的站点

    def dfs(node):
        visited.add(node)  # 将当前站点标记为已访问

        for i in range(n):
            if matrix[node][i] == '1' and i not in visited:
                dfs(i)  # 对与当前站点相连的未访问站点进行DFS遍历

    count = 0  # 初始广播站个数

    for i in range(n):
        if i not in visited:
            dfs(i)  # 对未访问的站点进行DFS遍历
            count += 1

    return count


# 主程序
matrix = input().split(',')  # 输入二维数组的各行，以逗号分隔行

result = min_stations(matrix)  # 调用函数计算最少广播站个数

print(result)  # 输出最少广播站个数