首页 > 试题广场 >

找出直系亲属

[编程题]找出直系亲属

热度指数：9254 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

如果A，B是C的父母亲，则A，B是C的parent，C是A，B的child，如果A，B是C的（外）祖父，祖母，则A，B是C的grandparent，C是A，B的grandchild，如果A，B是C的（外）曾祖父，曾祖母，则A，B是C的great-grandparent，C是A，B的great-grandchild，之后再多一辈，则在关系上加一个great-。

输入描述:

    输入包含多组测试用例,每组用例首先包含2个整数n（0<=n<=26）和m（0<m<50）, 分别表示有n个亲属关系和m个问题, 然后接下来是n行的形式如ABC的字符串，表示A的父母亲分别是B和C，如果A的父母亲信息不全，则用-代替，例如A-C,再然后是m行形式如FA的字符串,表示询问F和A的关系。

输出描述:

    如果询问的2个人是直系亲属，请按题目描述输出2者的关系，如果没有直系关系，请输出-。
    具体含义和输出格式参见样例.

示例1

输入

3 2
ABC
CDE
EFG
FA
BE

输出

great-grandparent
-

算法知识视频讲解

Python

风追司马

def find(x,y):
    ans=1
    global father
    tmp1=father[ord(x) - ord('A')]
    while tmp1!=father[tmp1]:
        if tmp1==ord(y)-ord('A'):
            return ans
        tmp1=father[tmp1]
        ans+=1
    if tmp1 == ord(y) - ord('A'):
        return ans
    return 0

while True:
    try:
        father=[i for i in range(26)]
        n,m=map(int,input().split())
        for i in range(n):
            s=input()
            if s[1]!='-':
                father[ord(s[1])-ord('A')]=ord(s[0])-ord('A')
            if s[2]!='-':
                father[ord(s[2])-ord('A')]=ord(s[0])-ord('A')
        ques=[]
        for i in range(m):
            ques.append(input())
        for i in ques:
            s=i
            x=find(s[0],s[1])
            y=find(s[1],s[0])
            flag=2
            if x>0 and y==0:
                flag=0         #s[0]是高辈分
            if x==0 and y>0:
                flag=1 #s[1]是高辈分
            tmp=max(x,y)
            if tmp==0:
                print('-')
                continue
            if tmp==1:
                if flag==0:
                    print("parent")
                else:
                    print("child")
            elif tmp==2:
                if flag == 0:
                    print('grandparent')
                else:
                    print("grandchild")
            else:
                tmp-=2
                if flag == 0:
                    ans='grandparent'
                else:
                    ans = 'grandchild'
                while tmp:
                    ans='great-'+ans
                    tmp-=1
                print(ans)
    except:
        exit()

发表于 2021-03-16 01:30:35 回复(0)