給出一組單詞，判斷是否可以將單詞排序，使得每個單詞的第一個字母和前一個單詞的最後一個字母相同。
輸入：
每個測試數據的第一行為整數N(1<=N<=10000)，接下來的N 行，每行為一個單詞，每個單詞都只包含小寫字母並且最多包含100 個字符。
輸出：
如果不能將單詞序列重組以滿足要求，則輸出一行”Impossible”，否則輸出”Possible”。
輸入樣例：
2
ok
ok
2
ok
ko
輸出樣例：
Impossible
Possible
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 //返回單詞最後一個字符。
6 char endOfString(char s[])
7 {
8 int i;
9
10 for(i=0; s[i+1]!='\0'; i++)
11 ;
12
13 return s[i];
14 }
15
16 //返回單詞第一個字符
17 char firstOfWord(char s[])
18 {
19 return s[0];
20 }
21
22 //打印所有的單詞
23 /*void print(char temp[][100],int N)
24 {
25 int i;
26 for(i=0; i<N; i++)
27 printf("%s\n",temp[i]);
28 }*/
29
30 //查看是不是可以拼接,可則返回1，否則返回0
31 int check(char temp[][100],int N)
32 {
33 int i,j,count=0,flag_pos=1,count_N=1;
34 char head,end;
35
36 head = firstOfWord(temp[0]);
37 end = endOfString(temp[0]);
38 strcpy(temp[0],"");
39
40 for(j=1; j<N; j++)
41 {
42 count=0;
43 for(i=1; i<N; i++)
44 {
45 if(strcmp(temp[i],"")==0)
46 continue;
47 else if(firstOfWord(temp[i])==end)
48 {
49 end = endOfString(temp[i]);
50 strcpy(temp[i],"");
51 count ++;
52 count_N++;
53 }
54 else if(endOfString(temp[i])==head)
55 {
56 head = firstOfWord(temp[i]);
57 count++;
58 strcpy(temp[i],"");
59 count_N++;
60 }
61 else
62 continue;
63 }
64
65 if(count==0)
66 {
67 flag_pos=0;
68 break;
69 }
70
71 if(count_N==N)
72 break;
73
74 }
75 return flag_pos;
76 }
77
78 int main()
79 {
80 int N,flag_pos,i;
81 char word[1000][100];
82
83 //printf("please input;\n");
84 scanf("%d",&N);
85 for(i=0; i<N; i++)
86 {
87 scanf("%s",word[i]);
88 }
89
90 flag_pos = check(word,N);
91 if(flag_pos==0)
92 printf("Impossible\n");
93 else
94 printf("Possible\n");
95
96 //print(word,N);
97 //printf("%s\n",word[0]);
98 //printf("The end of the word is %c\n",endOfString(word[0]));
99 //printf("The first of the word is %c\n",firstOfWord(word[0]));
100
101 return 0;
102 }
摘自 zhengmian
