题解 | 找出直系亲属(bfs)

题意：找出给定两个字符的血缘关系。

首先可以用一个数组p来记录各个字母的父母，p[i][0]表示父亲,p[i][1]表示母亲。初始值为'$'。

对于输入父母中的‘-’怎么处理？如果有一个父母信息缺失，那么我们不存入数组当中。

之后我们从下往上找到它的父亲，每找到一个先判断是不是需要找到的那个字符，如果不是同时也非'$'就加入队列当中，每上一层，辈分也增加一层，通过往上找的过程进行累加我们就可以知道a是b的第几层关系。

#include <iostream>
#include <queue>
using namespace std;
char p[100][2];

void init() {
    for (int i = 0; i < 100; i ++) {
        p[i][0] = '$';
        p[i][1] = '$';
    }
}
//用来判断a是否是b的父亲
int bfs(char a, char b) {
    queue<pair<char, int>> q;
    q.push({b, 0});
    while (!q.empty()){
        pair<char, int> t = q.front();
        q.pop();
        char c = t.first;
        for(int i = 0; i < 2; i ++){
		  //找到了
            if(p[c-'A'][i] == a) return t.second + 1;
		  //它上面已经没有辈分关系了
            else if(p[c - 'A'][i] == '$'){
                continue;
            }
		  //当前父母加入队列当中
            else{
                q.push({p[c - 'A'][i],t.second +1});
            }
        }
    }
    return -1;
}

int main() {
    int n, m;
    while (cin >> n >> m) { // 注意 while 处理多个 case
        init();
        while (n--) {
            char a, b, c;
            cin >> a >> b >> c;
            if (b != '-') p[a - 'A'][0] = b;
            if (c != '-') p[a - 'A'][1] = c;
            
        }
        while (m --) {
            char a, b;
            cin >> a >> b;
		  //a是不是b的父亲。
            int ab = bfs(a, b);
		  //b是不是a的父亲，因为是单向关系，只记录了父亲是谁，没有记录儿子是谁。
            int ba = bfs(b, a);
            if (ab == -1 && ba == -1) cout << "-" << endl;
            if (ab != -1 && ba == -1) {
                if (ab == 1) cout << "parent" << endl;
                else if (ab == 2) cout << "grandparent" << endl;
                else {
                    for (int i = 0; i < ab - 2; i ++) {
                        cout << "great-";
                    }
                    cout << "grandparent" << endl;
                }
            }
		  //b是a的父亲，那么a是b的儿子。
            if (ab == -1 && ba != -1) {
                if (ba == 1) cout << "child" << endl;
                else if (ba == 2) cout << "grandchild" << endl;
                else {
                    for (int i = 0; i < ba - 2; i ++) {
                        cout << "great-";
                    }
                    cout << "grandchild" << endl;
                }
            }
        }
    }
    return 0;
}