问题 : 找出直系亲属

落日映苍穹つ 2022-06-10 06:25 169阅读 0赞

题目描述  
如果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

## great-grandparent ##

AC代码

#include<cstdio>
    #include<iostream>
    using namespace std;
    const int INF=1000000000;
    
    int map[105][105];
    
    void Floyd() {
        for(int k = 1 ; k <= 100 ; k ++)
            for(int i = 1 ; i <= 100 ; i ++)
                for(int j = 1 ; j <= 100 ; j ++)
                    if(map[i][j] > map[i][k] + map[k][j])
                        map[i][j] = map[i][k] + map[k][j];
    }
    
    int minn(int x, int y) {
        return x < y ? x : y;
    }
    
    int main () {
        int n,m,i,j,a,b,c;
        char str[10];
        while(scanf("%d %d",&n,&m) && n + m) {
            for(i = 1 ; i <= 100 ; i ++)
                for(j = 1 ; j <= 100 ; j ++)
                    if(i == j)map[i][j] = 0;
                    else map[i][j] = INF;
            for(i = 1 ; i <= n ; i ++) {
                scanf("%s",str);
                a = str[0];
                b = str[1];
                c = str[2];
          //      cout<<a<<b<<c<<endl;
                map[a][b] = map[a][c] = 1;
            }
            Floyd();
            for(i = 1 ; i <= m ; i ++) {
                scanf("%s",str);
                a = str[0];
                b = str[1];
                c = minn(map[a][b],map[b][a]);
                if(c == INF || !c) {
                    printf("-\n");
                    continue;
                }
                if(c == 1) {
                    if(map[a][b] == 1)
                        printf("child\n");
                    else
                        printf("parent\n");
                } else {
                    if(map[a][b] != INF) {
                        c -= 2;
                        for(j = 1 ; j <= c ; j ++)
                            printf("great-");
                        printf("grandchild\n");
                    } else {
                        c -= 2;
                        for(j = 1 ; j <= c ; j ++)
                            printf("great-");
                        printf("grandparent\n");
                    }
                }
            }
        }
        return 0;
    }