HDOJ1181 字符串首尾相连问题[DFS（）+字符串排序strcmp（）||▲矩阵标记]

变形课

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 131072/65536K (Java/Other)

Total Submission(s) : 4 Accepted Submission(s) : 1

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

呃......变形课上Harry碰到了一点小麻烦,因为他并不像Hermione那样能够记住所有的咒语而随意的将一个棒球变成刺猬什么的,但是他发现了变形咒语的一个统一规律:如果咒语是以a开头b结尾的一个单词,那么它的作用就恰好是使A物体变成B物体.
Harry已经将他所会的所有咒语都列成了一个表,他想让你帮忙计算一下他是否能完成老师的作业,将一个B(ball)变成一个M(Mouse),你知道,如果他自己不能完成的话,他就只好向Hermione请教,并且被迫听一大堆好好学习的道理.

Input

测试数据有多组。每组有多行，每行一个单词,仅包括小写字母,是Harry所会的所有咒语.数字0表示一组输入结束.

Output

如果Harry可以完成他的作业,就输出"Yes.",否则就输出"No."(不要忽略了句号)

Sample Input

so
soon
river
goes
them
got
moon
begin
big
0

Sample Output

Yes.

Hint

Hint
Harry 可以念这个咒语:"big-got-them".

Source

Gardon-DYGG Contest 1

code：（TLE）我知道是自己剪枝没做好，也不知道如果事先不排序的话，是否一定会TLE，希望有人看到，给我指点一下啊！

 1 #include<iostream>
 2 using namespace std;
 3 
 4 char data[100][100];                         //数据
 5 int i;                                      //字符串个数
 6 int vst[100];                                //标记是否访问
 7 bool flag;                                  //是否已找到结果
 8 int count;                                 //记录已找到的单词数
 9 
10 void DFS(int tag)
11 {
12     int j;
13     if(count>=i)
14         return;
15     if(data[tag][strlen(data[tag])-1]=='m')                  //出现目标态
16     {
17         flag=true;
18         printf("Yes.\n");
19         return;
20     }
21     for(j=0;j<i;j++)
22     {
23         if(!vst[j]&&data[j][0]==data[tag][strlen(data[tag])-1])    //判断条件：1、未访问过；2、首尾相连
24         {
25             vst[j]=1;
26             count++;
27             DFS(j);
28             if(flag)
29                 return;
30             vst[j]=0;
31         }
32     }
33     return;
34 }
35 
36 int main()
37 {
38     int j;
39     int flag1;               //标记是否有以m结尾的字符串
40     int flag2;               //标记是否有以b开头的字符串
41     while(1)
42     {
43         i=0;
44         flag1=0;
45         flag2=0;
46         flag=false;
47         while(scanf("%s",data[i++]))
48         {
49             if(data[i-1][strlen(data[i-1])-1]=='m')
50                 flag1=1;
51             if(data[i-1][0]=='b')
52                 flag2=1;
53             if((data[i-1][0]-'0')==0)
54                 break;
55         }
56         if(flag1&&flag2)
57         {
58             for(j=0;j<i;j++)
59             {
60                 count=0;
61                 if(data[j][0]=='b')                     //找到以b开头的字符串为根
62                 {
63                     memset(vst,0,sizeof(vst));
64                     vst[j]=1;                           //标记
65                     DFS(j);
66                     if(flag)                            
67                         break;
68                 }
69             }
70         }
71         if(!flag||!flag1||!flag2)
72             printf("No.\n");
73     }
74     return 0;
75 }

别人的代码1：

DFS（）+字符串排序

 1 #include <stdio.h> 
 2 #include <stdlib.h> 
 3 #include <string.h> 
 4 #define N 1000 
 5 #define M 30 
 6 char ch[N][M]; 
 7 int visited[N],n; 
 8   
 9 int cmp(const void *a, const void *b) 
10 { 
11     char *c = (char *) a; 
12     char *d = (char *) b; 
13     return strcmp(c,d); 
14 } 
15   
16 int DFS_Visit(int cur,char *word) 
17 { 
18     int i,flag=0,len=strlen(word); 
19     visited[cur]=1;//对已经选择的单词进行标记 
20     if(word[len-1]=='m') flag=1; 
21     else
22         for(i=0;i<n;i++) 
23         { 
24             if(!visited[i]&&word[len-1]==ch[i][0])//搜索前提 
25                 if(DFS_Visit(i,ch[i])) 
26                 { 
27                     flag=1; 
28                 } 
29         } 
30     visited[cur]=0;//标记还原，以便上一层的搜索可以继续选择该单词 
31     return flag; 
32 } 
33   
34 int DFS() 
35 { 
36     int i; 
37     memset(visited,0,sizeof(visited)); 
38     qsort(ch,n,sizeof(ch[0]),cmp);//按字典序排列 
39     for(i=0;i<n;i++)//递归外层枚举以b为首的字母 
40     { 
41         if(ch[i][0]>'b') break;//首字母比b大的都不用搜索 
42         if(ch[i][0]=='b') 
43             if(DFS_Visit(i,ch[i])) 
44                 return 1; 
45     } 
46     return 0; 
47 } 
48   
49 int main() 
50 { 
51     int i=0; 
52 //  freopen("变形课.txt","r",stdin); 
53     while(gets(ch[i])!=NULL) 
54     { 
55         if(ch[i][0]=='0') 
56         { 
57             n=i,i=-1; 
58             if(DFS()) printf("Yes.\n"); 
59             else printf("No.\n"); 
60         } 
61         i++; 
62     } 
63     return 0; 
64 }

别人的代码2：（▲矩阵标记）

不错的思维方式！

虽然这代码过了测试数据，其实是不正确的

例如测试数据为：

另外说一句，杭电里的这道题测试数据是有缺陷的，如果你第一次输出的是Yes.，之后全部输出No.也能过了。

 1 #include<iostream>
 2 using namespace std;
 3 int main()
 4 {
 5     int i,j,k,len;
 6     char s[100],mark[30][30];             //s存数据，mark标记
 7     while(gets(s))
 8     {
 9         memset(mark,0,sizeof(mark));
10         while(s[0]!='0')
11         {
12             len=strlen(s);
13             mark[s[0]-'a'][s[len-1]-'a']=1;
14             gets(s);
15         }
16         for(k=0;k<26;k++)
17             for(i=0;i<26;i++)
18             {
19                 if(i!=k&&mark[k][i]==1)
20                 {
21                     for(j=0;j<26;j++)
22                         if(mark[k][j]||mark[i][j])
23                             mark[k][j]=1;
24                 }
25             }
26         if(mark[1][12]==1)
27             puts("Yes.");
28         else
29             puts("No.");
30     }
31     return 0;
32 }

别人的代码3：

很标准的代码，我的目标！

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <string>
 5 #include <algorithm>
 6 #include <iostream>
 7 using namespace std;
 8 const int N=110;
 9 
10 string str[N];
11 bool vis[N],flag;
12 int cnt;
13 
14 void dfs(char s)
15 {
16     if(s=='m')
17     {
18         flag=true; 
19         return ;
20     }
21     for(int i=0;i<cnt;i++)
22     {
23         if(str[i][0]==s&&!vis[i])
24         {
25             int len=str[i].length();
26             vis[i]=true;
27             dfs(str[i][len-1]);
28             vis[i]=false;
29         }
30     }
31 }
32 
33 int main(){
34     
35     // freopen("data.in","r",stdin);
36     // freopen("data.out","w",stdout);
37     
38     while(cin>>str[cnt])
39     { 
40         if(str[cnt]=="0")
41         {
42             memset(vis,false,sizeof(vis));
43             flag=false;
44             dfs('b');
45             if(flag) puts("Yes.");
46             else puts("No.");
47             cnt=0; 
48         } 
49         cnt++; 
50     }
51     return 0;
52 }

补充：

(一)strcmp函数

strcmp函数是比较两个字符串的大小,返回比较的结果。一般形式是：

i=strcmp(字符串，字符串);

其中，字符串１、字符串２均可为字符串常量或变量；i 是用于存放比较结果的整型变量。比较结果是这样规定的：

①字符串1小于字符串2,strcmp函数返回一个负值;

②字符串1等于字符串2,strcmp函数返回零;

③字符串1大于字符串2,strcmp函数返回一个正值;那么,字符中的大小是如何比较的呢?来看一个例子。

实际上,字符串的比较是比较字符串中各对字符的ASCII码。首先比较两个串的第一个字符，若不相等，则停止比较并得出大于或小于的结果；如果相等就接着比较第二个字符然后第三个字符等等。如果两上字符串前面的字符一直相等,像"disk"和"disks" 那样, 前四个字符都一样, 然后比较第五个字符, 前一个字符串"disk"只剩下结束符'/0',后一个字符串"disks"剩下's','/0'的ASCII码小于's'的ASCII 码,所以得出了结果。因此无论两个字符串是什么样，strcmp函数最多比较到其中一个字符串遇到结束符'/0'为止，就能得出结果。

注意:字符串是数组类型而非简单类型，不能用关系运算进行大小比较。

if("ABC">"DEF") /*错误的字符串比较*/

if(strcmp("ABC","DEF") /*正确的字符串比较*/

（二）strcpy函数

strcpy函数用于实现两个字符串的拷贝。一般形式是：

strcpy（字符中1,字符串2)

其中,字符串1必须是字符串变量,而不能是字符串常量。strcpy函数把字符串2的内容完全复制到字符串1中,而不管字符串1中原先存放的是什么。复制后，字符串2保持不变。

例:

注意,由于字符串是数组类型,所以两个字符串复制不通过赋值运算进行。

t=s; /*错误的字符串复制*/

strcpy(t,s); /*正确的字符串复制*/

心得：

     //    写代码要简洁，高效
     //    先对字符串数组进行排序
     //    strcmp()
     //    当题目做不出来时就给自己的代码写备注

If you have any questions about this article, welcome to leave a message on the message board.

Brad(Bowen) Xu
E-Mail : maxxbw1992@gmail.com