华为笔试20220907

1 猪的亲戚关系

农场里有n条猪，编号为0..n-1

给定m个列表，首元素是其余所有元素的母亲,每个元素只有一个母亲

给定两个编号x，y，求x，y的距离（如不联通输出-1，相同为0）

数据范围：

0<n<1e9

0<m<1e4

样例：

n = 10

a[0] = 0,1,2
表示0是1，2的母亲
a[1] = 1,3,4
表示1是3，4的母亲

求2，4的距离

存在路径2-0-1-4 答案为3

solution:

事实上就是找一条x到y的路径，一个简单的dfs就可以了

需要注意，因为n的范围很大，需要用哈希表存储边

但是我只过了90%，也不知道是为什么

n,m = map(int,input().split())
g = defaultdict(list)
for _ in range(m):
    nums = list(map(int,input().split()))
    x = nums[0]
    for y in nums[1:]:
        g[x].append(y)
        g[y].append(x)
m1,m2 = map(int,input().split())
def dfs(x,fa,res):
    for y in g[x]:
        if y != fa:
            if y == m2:
                return res+1
            tmp = dfs(y,x,res+1)
            if tmp != -1:
                return tmp
    return -1
print(dfs(m1,-1,0))

2 求士兵到敌人的最短耗时

给定一个m x n的二维表格，其实有一个S表示士兵，一个E表示敌人

其余的要么是B，表示街道可以通行，要么是X，表示禁止通行

士兵可以上下左右移动，移动一次耗时1

另外士兵转向时，额外耗时1

求士兵找到敌人的最短耗时，如找不到输出-1

数据范围:

1 < m,n < 1000

这题用bfs应该就可以做了，但是不知道为什么我脑子抽了用堆

但是我感觉堆应该也能实现啊，也有可能是我存储的变量太多

我的节点存了 (耗时，横坐标，纵坐标，之前的x方向，之前的y方向) 5个变量

只过了25%，其余超时了

事后想想，应该直接bfs的，然后后面两个方向可以合并成一个，横纵坐标也可以合并成一个 但是不知道超时的原因到底是什么 如今也没有再次测试的机会了

3 一直在前面两题，没看

总结

这是第一次做华子的笔试，感觉难度还行，就是网页不太好用

python需要缩进，特别难受，删除一个tab要按四下退格，真的难受