HDU 1181 变形课

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1181

此题多种方法。比如说Flyod传递闭包就能搞定这里只写DFS和BFS

熟悉下。只有DFS是我写的，其他的都是同学的。

DFS

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #define N 30
 5 int m[N][N],flag,visit[N];
 6 void dfs(int n)
 7 {
 8     int i;
 9     if(n=='m'-'a')
10     {
11         flag=1;return;
12     }
13     for(i=0;i<26;i++)
14     {
15        if(m[n][i]==1&&!visit[i])
16        {
17            visit[i]=1;
18            dfs(i);
19        }
20     }
21 }
22 int main()
23 {
24     char s[100];int len;
25     memset(m,0,sizeof(m));
26     memset(visit,0,sizeof(visit));
27     while(scanf("%s",s)&&s[0]!='0')
28     {
29         len=strlen(s);
30         m[s[0]-'a'][s[len-1]-'a']=1;
31         while(scanf("%s",s)&&s[0]!='0')
32         {
33             flag=0;
34             len=strlen(s);
35             m[s[0]-'a'][s[len-1]-'a']=1;
36         }
37         dfs(1);
38         flag== 1 ? printf( "Yes.\n" ) : printf( "No.\n" );
39     }
40     return 0;
41 }

BFS

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 int q[100000];
 4 int map[30][30];
 5 int pro[100000];
 6 int f,r;
 7 
 8 int main()
 9 {
10     int n,i,j,len,leap;
11     char s[200];
12     while(scanf("%s",s) != EOF)
13     {
14         leap = 0;
15         memset(map,0,sizeof(map));
16         memset(pro,0,sizeof(pro));
17         memset(q,0,sizeof(q));
18         len = strlen(s);
19         map[s[0]-'a'][s[len-1]-'a'] = 1;
20 
21         while(scanf("%s",s) != EOF)
22         {
23             len = strlen(s);
24             if(s[0] == '0')
25             break;
26             map[s[0]-'a'][s[len-1]-'a'] = 1;
27         }
28         f = 0,r = 0;
29         q[r++] = 'b'-'a';
30         while(f < r)
31         {
32             int v;
33             v = q[f++];
34             for(i = 0;i < 26;i++)
35             {
36                 if(map[v][i] && !pro[i])
37                 {
38                     if(i == 'm'-'a')
39                     {
40                         leap = 1;
41                         break;
42                     }
43                     q[r++] = i;
44                     pro[i] = 1;
45                 }
46             }
47             if(leap)
48             break;
49         }
50         if(leap)
51         puts("Yes.");
52         else
53         puts("No.");
54     }
55     return 0;
56 }

用STL queue实现队列的 BFS

View Code

 1 #include <queue> 
 2 #include <cstdio> 
 3 #include <cstring> 
 4 #include <iostream> 
 5 using namespace std; 
 6 
 7 const int N=1001; 
 8 int map[N][N]; 
 9 int vis[N]; 
10 queue<int>q; 
11 
12 int bfs() 
13 { 
14     while(!q.empty()) 
15     { 
16         int a; 
17         a=q.front(); 
18         q.pop(); 
19         for(int i=0;i<26;i++) 
20         { 
21             if(map[a][i]&&!vis[i]) 
22             { 
23                 if(i=='m'-'a') 
24                 { 
25                     return 1; 
26                 } 
27                 q.push(i); 
28                 vis[i]=1; 
29             } 
30         } 
31     } 
32     return 0; 
33 } 
34 
35 int main() 
36 { 
37     int len; 
38     char s[N]; 
39     while(~scanf("%s",s)) 
40     { 
41         while(!q.empty()) 
42             q.pop(); 
43         memset(map,0,sizeof(map)); 
44         memset(vis,0,sizeof(vis)); 
45         len=strlen(s); 
46         map[s[0]-'a'][s[len-1]-'a']=1; 
47         while(~scanf("%s",s)) 
48         { 
49             len=strlen(s); 
50             if(s[0]=='0') 
51                 break; 
52             map[s[0]-'a'][s[len-1]-'a']=1; 
53         } 
54         q.push('b'-'a'); 
55         if(bfs()) 
56             puts("Yes."); 
57         else 
58             puts("No."); 
59     } 
60     return 0; 
61 }