ZeroJudge K862: 輩份比較

文文的老家是個大家族，每次過年回老家時總是搞不清楚輩份關係，常常把長輩當平輩，講話沒大沒小。於是爸爸拿出家譜來，好好地跟文文複習一次家族成員之間的輩份關係。

現在，從這份家譜中取出兩個人的名字，請你比較他們的輩份關係。

範例測資

範例輸入範例輸出
輸入的第一行含有一個整數 N (1 ≤ N ≤ 100)，代表這份家譜中包含了幾個親子關係。
接下來有 N 行，每行有兩個名字 a 和 b，代表 a 是 b 的孩子。
最後有一行查詢，含有兩個名字 p 和 q，代表我們希望知道 p 跟 q 之間的輩份關係。
保證族譜中的每一個人都可以追溯到一個共同的祖先。		輸出一個整數，p 和 q 同輩時，輸出 0。p 是 q 的長輩的話，輸出一個正整數，代表 p 是 q 上面幾代的長輩。p 是 q 的晚輩的話，輸出一個負整數，代表 p 是 q 下面幾代的晚輩。
3
Jacob Isaac
Isaac Abraham
Ishmael Abraham
Jacob Ishmael		-1
3
A ABC
B ABC
C ABC
A C		0
4
me dad
dad grand-dad
son me
grand-son son
grand-dad grand-son		4
ZeroJudge K862 範例測資

解題思路

本題類似於樹狀圖的概念，可以創建一個 Struct，裡面存名字、長輩、和晚輩。然後再利用 Map 來將名字當成Key把這些 Struct 存進來。最後再使用 BFS 的方式從要找的名字開始往上和往下找，要注意的是，需要再使用一個 Map 來紀錄目前這個名字是否有被走過了以免進行重複的運算。

範例程式碼－ZeroJudge K862: 輩份比較

#include <iostream>
#include <map>
#include <vector>
using namespace std;

struct node
{
    vector<node*>up;
    vector<node*>down;
    string name;
    int val = 0;
};

map<string, node*>MAP;
map<string, int>walk;
string start, target;
int ans;

void BFS(vector<string>start)
{
    if (start.size() == 0) return;
    vector<string>newStart;
    for (int i = 0; i<start.size(); i++)
    {
        string name = start[i];
        walk[name] = 1;
        if (name == target)
        {
            ans = MAP[name]->val;
            return;
        }
        if (MAP[name]->up.size() != 0)
        {
            for (int j = 0; j<MAP[name]->up.size(); j++)
            {
                string fn = MAP[name]->up[j]->name;
                if (walk[fn] == 0) {
                    MAP[fn]->val = MAP[name]->val - 1;
                    newStart.push_back(fn);
                }
            }
        }
        if (MAP[name]->down.size() != 0)
        {
            for (int j = 0; j<MAP[name]->down.size(); j++)
            {
                string fn = MAP[name]->down[j]->name;
                if (walk[fn] == 0) {
                    MAP[fn]->val = MAP[name]->val + 1;
                    newStart.push_back(fn);
                }
            }
        }
    }
    BFS(newStart);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    for (int i = 0; i<N; i++)
    {
        string a, b;
        cin >> a >> b;
        if (MAP[a] == nullptr)
        {
            node* tmp = new node();
            tmp->name = a;
            MAP[a] = tmp;
        }
        if (MAP[b] == nullptr)
        {
            node* tmp = new node();
            tmp->name = b;
            MAP[b] = tmp;
        }
        MAP[a]->up.push_back(MAP[b]);
        MAP[b]->down.push_back(MAP[a]);
    }
    cin >> start >> target;
    vector<string>v;
    v.push_back(start);
    BFS(v);
    cout << ans << "\n";
}

//ZeroJudge K862
//Dr. SeanXD
標籤

相關文章

發佈留言