ZeroJudge A584: Relative Relations

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

ZeroJudge A584題目解說用圖

To simplify the problem, we made the following restrictions:

  1. We represent both parents by the name of the father, and both grandparents by the name of the grandfather.
  2. Each node will have a number of child nodes depending on the number of biological children associated with that node's name, but it will not exceed ten at most.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The input consists of N+2 lines (1 ≤ N ≤ 50). The first line contains only one value, N, indicating there are N records to build the tree structure. The 2nd to the N+1 lines each contain one record. In each record, the first English name is the name of a node, and the subsequent English names are the names of the child nodes of that node. Names are separated by spaces, and there is no order relationship between the records, but a tree structure can always be constructed. The last line of input contains the names of two different individuals for determining their degree of kinship (these names will appear in the input data), separated by a space. In the input data, all English names consist of three uppercase letters.Please output a number representing the degree of relationship between the two individuals.
3
PAM BOB TOM PAT
BOB LIZ ANN
PAT JIM
LIZ TOM		3
2
BOB LIZ ANN
PAM BOB TOM
LIZ ANN		2

Thought Process

Use a Map to store the relationships of each person, utilize StringStream to split strings, and employ BFS to find the starting point for each search for individuals.

Sample Code－ZeroJudge A584: Relative Relations

#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
Tags

Related Posts

Comments