ZeroJudge A584: 親等關係

社會老師在小明的班上請同學們討論法律上的一等親二等親三等親如何區分與計算，並於下一堂課進行報告。小明在網路上找到一個計算親等的建議方式–畫樹狀圖，圖中每一個節點代表一個人名，該節點的父節點則存放他父親的名字，而該節點的子節點則存放他的小孩的名字。在樹狀圖中二個親屬之間需經幾條的連結 (Link) 才能連接就是幾等親。例如下圖中，LIZ 和他的父親 BOB 之間只需經過一條連結，所以是一等親，而 LIZ 和他的爺爺 PAM 就需經過二條連結，是二等親。另外，LIZ 需經過四條連結才能與和 JIM 相連，所以就是四等親了。你能寫一個程式自動判斷二個人之間的親等關係嗎?

ZeroJudge A584 題目解說用圖

為了簡化問題，我們做了以下限制：

  1. 我們以父親的名字來代表父母親雙方，且以祖父的名字來代表祖父母雙方。
  2. 每一個節點會有多少個子節點視存入該節點的人名有多少個親生子女而定，但最多不會超過十個。

範例測資

範例輸入範例輸出
輸入包含了 N+2 行 (1 ≤ N ≤ 50)，第一行輸入只有一個 N 值，表示共有 N 筆資料以供建立樹狀圖。第 2 行至第 N+1 行則分別輸入 N 筆資料，每筆資料中，第一個英文名字為某一節點的名字，其後的英文名字為該節點之子節點的名字，每個名字之間以空白隔開，各筆資料之間沒有前後順序關係，但一定可以建出一樹狀圖。最後一行輸入則是要判斷親等關係的二個不同人的名字 (該名字一定會出現在輸入之資料中)，名字之間亦以空白隔開。在輸入資料中，所有的英文名字都以 3 個大寫英文字母命名。請輸出一個數字，代表該二人間的親等關係。
3
PAM BOB TOM PAT
BOB LIZ ANN
PAT JIM
LIZ TOM		3
2
BOB LIZ ANN
PAM BOB TOM
LIZ ANN		2

解題思路

使用 Map 來存每個人他跟誰有關係，使用 StringStream 來切割字串，並且使用 BFS 來找每一次尋找人的起點。

範例程式碼－ZeroJudge A584: 親等關係

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

map<string, vector<string>>MAP;
map<string, int>walk;
int counts = 0;

void BFS(vector<string>start, string target)
{
    if (start.size() == 0) return;
    vector<string>newStart;
    for (int i = 0; i<start.size(); i++)
    {
        if (start[i] == target) return;
        vector<string>v = MAP[start[i]];
        walk[start[i]] = 1;
        for (int j = 0; j<v.size(); j++)
        {
            if (walk[v[j]] == 0) newStart.push_back(v[j]);
        }
    }
    counts++;
    BFS(newStart, target);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    string tmp;
    getline(cin, tmp);
    for (int i = 0; i<N; i++)
    {
        string str;
        getline(cin, str);
        stringstream ss;
        ss.clear();
        ss<<str;
        bool first = true;
        string start;
        while (true)
        {
            string s;
            ss>>s;
            if (ss.fail()) break;
            if (first)
            {
                start = s;
                first = false;
            }
            else
            {
                MAP[start].push_back(s);
                MAP[s].push_back(start);
            }
        }
    }
    string a, b;
    cin >> a >> b;
    vector<string>v;
    v.push_back(a);
    BFS(v, b);
    cout << counts << "\n";
}

//ZeroJudge A584
//Dr. SeanXD
標籤

相關文章

發佈留言