Posted on 2008-08-19 19:49
Hero 閱讀(272)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //1506 Accepted 572K 250MS C++ 3223B
2
3 //求出傳遞閉包后，a對應的密碼的outdeg應該為(inn-1)，b->(inn-2)
4 //然后用pwd2word[]建立映射
5
6 //以后注意特殊數據--比如要解密的單詞中根本沒有加密的字母
7
8 #include <stdio.h>
9 #include <stdlib.h>
10 #include <string.h>
11
12 const int size = 300 ;
13
14 int edge[size][size] ;
15 int indeg[size] ;
16 int outdeg[size] ;
17
18 int text2pwd[size] ;//文本到對應密碼的轉換
19 int pwd2text[size] ;//密碼到對應文本的轉換
20
21 char fword[300000] ; char sword[300000] ;
22 int flen = 0 ; int slen = 0 ;
23
24 int inn, inp, testnum ;
25
26 bool can = true ;
27
28 void input()
29 {
30 memset( edge, 0, sizeof(edge) ) ;
31
32 scanf( "%d %d", &inn, &inp ) ;
33
34 scanf( "%s", fword ) ;
35 for( int i=2; i<=inp; i++ ) {
36 scanf( "%s", sword ) ;
37 flen = strlen( fword ) ; slen = strlen( sword ) ;
38 int k = 0 ; for( k=0; fword[k]==sword[k]&&k<slen&&k<flen; k++ ) ;//找到第一個不相同的字母
39 if( k < flen && k < slen ) {
40 edge[fword[k]-'a'+1][sword[k]-'a'+1] = 1 ;//建圖
41 }
42 strcpy( fword, sword ) ;
43 }
44 //scanf( "%s", fword ) ;//最惡心的數據輸入(At the next line is encrypted message.)
45 getchar() ;//注意輸入的一個text不是一個字符串
46 gets( fword ) ;//別忘了getchar() ;
47 }
48
49 void f_indeg()
50 {
51 memset( indeg, 0, sizeof(indeg) ) ;
52 for( int sn=1; sn<=inn; sn++ ) {
53 for( int en=1; en<=inn; en++ ) {
54 if( edge[en][sn] ) indeg[sn]++ ;
55 }
56 edge[sn][sn] = 0 ;
57 }//構建indeg[]入度
58 }
59
60 void f_outdeg()
61 {
62 memset( outdeg, 0, sizeof(outdeg) ) ;
63 for( int sn=1; sn<=inn; sn++ ) {
64 for( int en=1; en<=inn; en++ ) {
65 if( sn!=en&&edge[sn][en] ) outdeg[sn]++ ;
66 }
67 }
68 }
69
70 void process()
71 {
72
73 bool haspwd = false ;
74 flen = strlen( fword ) ;
75 for( int i=0; i<flen; i++) {//判斷是否真的加密了--沒有也過了
76 if( fword[i]>='a'&&fword[i]<'a'+inn ) { haspwd = true ; break ; }
77 }
78 if( !haspwd ) { printf( "%s\n", fword ) ; return ; }
79
80 for( int k=1; k<=inn; k++ ) {//求傳遞閉包
81 for( int i=1; i<=inn; i++ ) {
82 for( int j=1; j<=inn; j++ ) {
83 if( edge[i][k] && edge[k][j] ) {
84 edge[i][j] = 1 ;
85 }
86 }
87 }
88 }
89
90 can = true ;//假定可以解密
91 for( int i=1; i<=inn; i++ ) {//判斷是否存在環
92 if( edge[i][i] ) { can = false ; break ; }
93 }
94 for( int i=1; i<=inn; i++ ) {//判斷是否存在孤立點
95 if( !can ) break ;
96 for( int j=1; j<=inn; j++ ) {
97 if( i == j ) continue ;
98 if( 0==edge[i][j]&&0==edge[j][i] )
99 { can = false ; break ; }
100 }
101 }
102
103 if( !can ) { printf( "Message cannot be decrypted.\n" ) ; return ; }
104
105 f_outdeg() ;
106
107 memset( text2pwd, -1, sizeof(text2pwd) ) ;
108 memset( pwd2text, -1, sizeof(pwd2text) ) ;
109
110 for( int i=1; i<=inn; i++ ) {//建立文本和密文的相互映射
111 int cnt = 0 ; int num = 0 ;
112 for( int k=1; k<=inn; k++ ) if( (inn-i)==outdeg[k] ) { cnt++ ; num=k ; }
113 if( 1 == cnt ) { text2pwd[i] = num ; pwd2text[num] = i ; }
114 }
115
116 flen = strlen( fword ) ;
117 for( int i=0; i<flen; i++ )
118 {
119 if( fword[i]>='a'&&fword[i]<'a'+inn )
120 {
121 int curnode = fword[i] - 'a' + 1 ;
122 if( pwd2text[curnode]<0 ) { can = false; break ; }
123 fword[i] = pwd2text[curnode] + 'a' - 1 ;
124 }
125 }
126
127 if( can ) printf( "%s\n", fword ) ;
128 else printf( "Message cannot be decrypted.\n" ) ;
129 }
130
131
132 int main()
133 {
134 //while( scanf( "%d", &testnum ) != EOF )
135 scanf( "%d", &testnum ) ;
136 {
137 for( int ct=1; ct<=testnum; ct++ )
138 {
139 input() ;
140
141 process() ;
142
143 //output() ;
144 }//for(ct)
145 }//while
146
147 return 0 ;
148 }
149