HDU 3786 직계 친족 찾기 dfs 검색

직계 친족 을 찾아내다
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1164    Accepted Submission(s): 482
Problem Description
A, B 가 C 의 부모 라면 A, B 는 C 의 parent, C 는 A, B 의 child, A, B 가 C 의 (외) 할아버지, 할머니 라면 A, B 는 C 의 grandparent, C 는 A, B 의 grandparent, A, B 의 grandschild, A, B 가 C 의 (외) 증조부, 증조 모 라면 A, B 는 C 의 great - grandparent, C 는 A, B 의 great - grandschild, 그 다음 에 한 세대 가 더 있 으 면 관계 에 great - 를 추가 합 니 다.
 
Input
여러 그룹의 테스트 용례 를 포함 하 는 것 을 입력 하 십시오. 각 그룹의 용례 는 먼저 정수 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 일 때 입력 을 끝 냅 니 다.
 
Output
2 명 이 직계 친족 이 라면 수출 2 자의 관 계 를 제목 대로 설명 하고 직계 관계 가 없 으 면 수출 -.
구체 적 인 의미 와 출력 형식 은 샘플 을 참조 합 니 다.
 
Sample Input

   
   
   
   

    
    
    
    3 2
ABC
CDE
EFG
FA
BE
0 0
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    great-grandparent
-
   
   
   
   

 
분명 한 검색 문 제 는 제 가 dfs 로 풀 었 습 니 다. 먼저 찾 아 보 세 요. 아버지 세대 의 관계 라 는 것 을 알 게 되면 찾 지 못 하고 뒤 집어 보 세 요. 이것 이 바로 자식 세대 의 관계 입 니 다. 관계 가 있 으 면 관계 의 깊이 를 얻 고 그 다음 에 수출 할 때 몇 가 지 를 주의해 야 합 니 다.

#include <cstdio>
#include <climits>

const int MAX = 'Z'+1;


char dic[MAX][2];

void init(){
	int i;

	for(i='A';i<MAX;++i){
		dic[i][0]=dic[i][1]='-';
	}
}

int min(int a,int b){
	if(a>b)a = b;
	return a;
}

int dfs(char ca,char cb,int level){
	if(ca=='-')return INT_MAX;

	if(ca==cb)return level+1;

	int la,lb;
	la = dfs(dic[ca][0],cb,level+1);
	lb = dfs(dic[ca][1],cb,level+1);

	return min(la,lb);
}

void print(int cnt,bool mark){
	if(mark){
		if(cnt==2){
			printf("child
");
		}else{
			while(cnt>3){
				printf("great-");
				--cnt;
			}
			printf("grandchild
");
		}
	}else{
		if(cnt==2){
			printf("parent
");
		}else{
			while(cnt>3){
				printf("great-");
				--cnt;
			}
			printf("grandparent
");
		}
	}
}

int main(){
	int n,m,i,cnt;
	bool mark;
	char ca,cb,cc;

	while(scanf("%d %d%*c",&n,&m)){
		if(n==0 && m==0)break;
		init();
		for(i=0;i<n;++i){
			scanf("%c%c%c%*c",&ca,&cb,&cc);
			dic[ca][0] = cb;
			dic[ca][1] = cc;
		}
		for(i=0;i<m;++i){
			scanf("%c%c%*c",&ca,&cb);
			mark = true;
			cnt = dfs(ca,cb,0);//      
			if(cnt==INT_MAX){//         
				mark = false;
				cnt = dfs(cb,ca,0);//    
			}
			if(cnt==INT_MAX){
				printf("-
");
				continue;
			}
			print(cnt,mark);
		}
	}
	return 0;
}