hdu4545 魔法串

魔法串

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1846    Accepted Submission(s): 692

Problem Description

　　小明和他的好朋友小西在玩一个新的游戏，由小西给出一个由小写字母构成的字符串，小明给出另一个比小西更长的字符串，也由小写字母组成，如果能通过魔法转换使小明的串和小西的变成同一个，那么他们两个人都会很开心。这里魔法指的是小明的串可以任意删掉某个字符，或者把某些字符对照字符变化表变化。如：
　　　　小西的串是 abba;
　　　　小明的串是 addba; 
　　　　字符变化表 d b （表示d能转换成b）。
　　那么小明可以通过删掉第一个d，然后将第二个d转换成b将串变成abba。

　　现在请你帮忙判断：他们能不能通过魔法转换使两个人的串变成一样呢？

 

Input

　　首先输入T，表示总共有T组测试数据(T <= 40)。
　　接下来共T组数据，每组数据第一行输入小西的字符串，第二行输入小明的字符串（数据保证字符串长度不超过1000，小明的串的长度大于等于小西的，且所有字符均为小写字母）。接着输入字母表，先输入m，表示有m个字符变换方式（m< = 100），接着m行每行输入两个小写字母，表示前一个可以变为后一个（但并不代表后一个能变成前一个）。

 

Output

　　对于每组数据，先输出Case数。
　　如果可以通过魔法转换使两个人的串变成一样，输出“happy”，
　　否则输出“unhappy”。
　　每组数据占一行，具体输出格式参见样例。

 

Sample Input

2 abba addba 1 d b a dd 0

 

Sample Output

Case #1: happy Case #2: unhappy

 

 

Recommend

liuyiding   |   We have carefully selected several similar problems for you

 

​ ​Statistic​​ | 

​ ​Submit​​ | 

​ ​Discuss​​ | 

​ ​Note​​

同学问我的。根据她的代码改的。

登录后复制

      
      

       
       #include<stdio.h>
       
       

       
       #include<string.h>
       
       

       
       char 
       
       stra[
       
       1010],
       
       strb[
       
       1010],
       
       a[
       
       110],
       
       b[
       
       110];
       
       

       
       int 
       
       main(){
       
       
    
       
       int 
       
       t,
       
       num
       
       =
       
       0,
       
       alen,
       
       blen,
       
       m,
       
       i,
       
       j,
       
       n;
       
       
    
       
       scanf(
       
       "%d",
       
       &
       
       t);
       
       
    
       
       while(
       
       t
       
       --)
       
       
    {
       
       
        
       
       int 
       
       k
       
       =
       
       0,
       
       flag
       
       =
       
       1;
       
       
        
       
       num
       
       ++;
       
       
        
       
       memset(
       
       a,
       
       0,
       
       sizeof(
       
       a));
       
       
        
       
       memset(
       
       b,
       
       0,
       
       sizeof(
       
       b));
       
       
        
       
       scanf(
       
       "%s %s",
       
       stra,
       
       strb);    
       
       
        
       
       alen
       
       =
       
       strlen(
       
       stra); 
       
       blen
       
       =
       
       strlen(
       
       strb); 
       
       
        
       
       scanf(
       
       "%d",
       
       &
       
       m);    
       
       
        
       
       while(
       
       m
       
       --)
       
       
        {
       
       
            
       
       scanf(
       
       " %c %c",
       
       &
       
       b[
       
       k],
       
       &
       
       a[
       
       k]);  
       
       
            
       
       k
       
       ++;
       
       
        }
       
       
        
       
       int 
       
       flag2;
       
       
        
       
       for(
       
       i
       
       =
       
       0,
       
       j
       
       =
       
       0;
       
       i
       
       <
       
       alen
       
       &&
       
       j
       
       <
       
       blen;)
       
       
        {  
       
       
            
       
       flag2
       
       =
       
       0;
       
       
            
       
       if(
       
       stra[
       
       i]
       
       !=
       
       strb[
       
       j])
       
       
            {     
       
       
                
       
       for(
       
       n
       
       =
       
       0;
       
       n
       
       <
       
       k;
       
       n
       
       ++)
       
       
                {      
       
       
                    
       
       if(
       
       strb[
       
       j]
       
       ==
       
       b[
       
       n]
       
       &&
       
       stra[
       
       i]
       
       ==
       
       a[
       
       n]) 
       
       
                        {
       
       
                            
       
       i
       
       ++,
       
       j
       
       ++,
       
       flag2
       
       =
       
       1;
       
       
                            
       
       break;
       
       
                        }      
       
       
                    }
       
       
                
       
       if(
       
       !
       
       flag2)
       
       
                
       
       j
       
       ++;
       
       
           }
       
       
            
       
       else
       
       
            
       
       i
       
       ++,
       
       j
       
       ++; 
       
       
        }
       
       
        
       
       if(
       
       i
       
       ==
       
       alen) 
       
       
            
       
       printf(
       
       "Case #%d: happy\n",
       
       num); 
       
       
        
       
       else
       
       
            
       
       printf(
       
       "Case #%d: unhappy\n",
       
       num);
       
       
    }
       
       
    
       
       return 
       
       0;
       
       
}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.
       
       
17.
       
       
18.
       
       
19.
       
       
20.
       
       
21.
       
       
22.
       
       
23.
       
       
24.
       
       
25.
       
       
26.
       
       
27.
       
       
28.
       
       
29.
       
       
30.
       
       
31.
       
       
32.
       
       
33.
       
       
34.
       
       
35.
       
       
36.
       
       
37.
       
       
38.
       
       
39.
       
       
40.
       
       
41.
       
       
42.
       
       
43.
       
       
44.
       
       
45.
       
       
46.
       
       
47.