首页 > ACM题库 > 九度OJ > 九度-1035-找出直系亲属[解题代码]
2013
12-12

九度-1035-找出直系亲属[解题代码]

题目来源:2009年浙江大学计算机及软件工程研究生机试真题

题目描述:
    如果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,之后再多一辈,则在关系上加一个great-。
输入:
    输入包含多组测试用例,每组用例首先包含2个整数n(0<=n<=26)和m(0<m<50), 分别表示有n个亲属关系和m个问题, 然后接下来是n行的形式如ABC的字符串,表示A的父母亲分别是B和C,如果A的父母亲信息不全,则用-代替,例如A-C,再然后是m行形式如FA的字符串,表示询问F和A的关系。
    当n和m为0时结束输入。
输出:
    如果询问的2个人是直系亲属,请按题目描述输出2者的关系,如果没有直系关系,请输出-。
    具体含义和输出格式参见样例.
样例输入:
3 2
ABC
CDE
EFG
FA
BE
0 0
样例输出:
great-grandparent
-

java 代码如下:
import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;

public class Main{
	static final int MAX = Integer.MAX_VALUE;
	static int son[];
	public static void main(String[] args) {
		Scanner s = new Scanner(new BufferedInputStream(System.in));
		while(s.hasNextInt()){
			int n = s.nextInt();
			int m = s.nextInt();
			if(n==0 && m==0)
				break;
			son = new int[1000];
			Arrays.fill(son, MAX);
			for(int i=0; i<n; i++){
				String str = s.next();
				int c1 = str.charAt(0)- 'A';
				char char2 = str.charAt(1);
				char char3 = str.charAt(2);
				if(char2 != '-'){
					int c2 = char2 - 'A';
					son[c2] = c1;
				}
				if(char3 != '-'){
					int c3 = char3 - 'A';
					son[c3] = c1;
				}
			}
			for(int i=0; i<m; i++){
				String str = s.next();
				int c1 = str.charAt(0)-'A';
				int c2 = str.charAt(1)-'A';
				int count = find(c1, c2);
				String ss2 = "grandparent";
				String ss1 = "parent";
				if(count ==0 || count == MAX){
					System.out.println("-");
					continue;
				}else if(count < 0){
					ss2 = "grandchild";
					ss1 = "child";
					count = -count;
				}
				if(count == 1){
					System.out.println(ss1);
					continue;
				}else if(count == 2){
					System.out.println(ss2);
					continue;
				}
				else if(count >2){
					for(int j=2; j<count; j++)
						ss2 = "great-"+ss2;
					System.out.println(ss2);
					continue;
				}
			}
		}
	}

	private static int find(int cc1, int cc2) {
		int count = 0;
		int c1 = cc1,c2 = cc2;
		while(son[c1] != MAX){
			c1 = son[c1];
			count ++;
			if(c1 == c2)
				return count;
		}
		c1 = cc1;
		count = 0;
		while(son[c2] != MAX){
			c2 = son[c2];
			count -- ;
			if(c2 == c1)
				return count;
		}
		return 0;
	}
	
}

/**************************************************************
	Problem: 1035
	User: coder
	Language: Java
	Result: Accepted
	Time:160 ms
	Memory:15956 kb
****************************************************************/


  1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确