題意:
找出直系親屬
Time Limit: 2000/1000 MS (Java/Others) ? ?Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1189 ? ?Accepted Submission(s): 493




Problem Description
如果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，之后再多一輩，則在關(guān)系上加一個great-。
?


Input
輸入包含多組測試用例,每組用例首先包含2個整數(shù)n（0<=n<=26）和m（0<m<50）, 分別表示有n個親屬關(guān)系和m個問題, 然后接下來是n行的形式如ABC的字符串，表示A的父母親分別是B和C，如果A的父母親信息不全，則用-代替，例如A-C,再然后是m行形式如FA的字符串,表示詢問F和A的關(guān)系。
當(dāng)n和m為0時結(jié)束輸入。
?


Output
如果詢問的2個人是直系親屬，請按題目描述輸出2者的關(guān)系，如果沒有直系關(guān)系，請輸出-。
具體含義和輸出格式參見樣例.
?


Sample Input
3 2
ABC
CDE
EFG
FA
BE
0 0
?


Sample Output
great-grandparent
-
?


思路:

? ? ? ?我用的是Floyd處理了一遍,也可以直接搜索處理,怎么都行,題簡單,數(shù)據(jù)簡單,隨意怎么寫,只要能記錄兩點(diǎn)之間的距離就行了,還有就是一定是有向圖,還有個提示就是輸入的不一定只是26個大寫字母,一開始一看26就直接自己默認(rèn)了,結(jié)果wa了好幾次,丟臉啊..

#include<stdio.h>#define 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){//getchar(); 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);// getchar(); a = str[0];b = str[1];c = str[2];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){puts("-");continue;}if(c == 1){if(map[a][b] == 1) puts("child");else puts("parent");}else{if(map[a][b] != INF){c -= 2;for(j = 1 ;j <= c ;j ++)printf("great-");puts("grandchild");}else{c -= 2;for(j = 1 ;j <= c ;j ++)printf("great-");puts("grandparent");}}}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu3786 Floyd或搜索 水题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。