Posted on 2008-08-19 19:27
Hero 閱讀(131)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
//Accepted 2003 C++ 00:00.46 1344K
//求出傳遞閉包后，a對應的密碼的outdeg應該為(inn-1)，b->(inn-2)
//然后用pwd2word[]建立映射
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int size = 300 ;
int edge[size][size] ;
int indeg[size] ;
int outdeg[size] ;
int text2pwd[size] ;//文本到對應密碼的轉換
int pwd2text[size] ;//密碼到對應文本的轉換
char fword[300000] ; char sword[300000] ;
int flen = 0 ; int slen = 0 ;
int inn, inp, testnum ;
bool can = true ;
void input()
{
memset( edge, 0, sizeof(edge) ) ;
scanf( "%d %d", &inn, &inp ) ;
scanf( "%s", fword ) ;
for( int i=2; i<=inp; i++ ) {
scanf( "%s", sword ) ;
flen = strlen( fword ) ; slen = strlen( sword ) ;
int k = 0 ; for( k=0; fword[k]==sword[k]&&k<slen&&k<flen; k++ ) ;//找到第一個不相同的字母
if( k < flen && k < slen ) {
edge[fword[k]-'a'+1][sword[k]-'a'+1] = 1 ;//建圖
}
strcpy( fword, sword ) ;
}
//scanf( "%s", fword ) ;//最惡心的數據輸入(At the next line is encrypted message.)
getchar() ;//注意輸入的一個text不是一個字符串
gets( fword ) ;//別忘了getchar() ;
}
void f_indeg()
{
memset( indeg, 0, sizeof(indeg) ) ;
for( int sn=1; sn<=inn; sn++ ) {
for( int en=1; en<=inn; en++ ) {
if( edge[en][sn] ) indeg[sn]++ ;
}
edge[sn][sn] = 0 ;
}//構建indeg[]入度
}
void f_outdeg()
{
memset( outdeg, 0, sizeof(outdeg) ) ;
for( int sn=1; sn<=inn; sn++ ) {
for( int en=1; en<=inn; en++ ) {
if( sn!=en&&edge[sn][en] ) outdeg[sn]++ ;
}
}
}
void process()
{
for( int k=1; k<=inn; k++ ) {//求傳遞閉包
for( int i=1; i<=inn; i++ ) {
for( int j=1; j<=inn; j++ ) {
if( edge[i][k] && edge[k][j] ) {
edge[i][j] = 1 ;
}
}
}
}
int cnt = 0 ;
for( int i=1; i<=inn; i++ ) {
cnt = 0 ;//計算i的入度
for( int j=1; j<=inn; j++ ) {
if( i == j ) continue ;
if( edge[i][j] ) cnt++ ;
if( 0==edge[i][j]&&0==edge[j][i] ) {//存在孤立點
cnt = -1 ; break ;
}
}
if( -1 == cnt ) pwd2text[i] = -1 ;
else pwd2text[i] = inn - cnt ;
}
flen = strlen( fword ) ; int i = 0 ;
for( i=0; i<flen; i++ )
{
if( fword[i]>='a'&&fword[i]<'a'+inn ) {
int curnode = fword[i] - 'a' + 1 ;
if( -1 != pwd2text[curnode] )
fword[i] = pwd2text[curnode] + 'a' - 1 ;
else break ;
}
}
if( i == flen ) printf( "%s\n", fword ) ;
else printf( "Message cannot be decrypted.\n" ) ;
}
int main()
{
//while( scanf( "%d", &testnum ) != EOF )
scanf( "%d", &testnum ) ;
{
for( int ct=1; ct<=testnum; ct++ )
{
input() ;
process() ;
//output() ;
}//for(ct)
}//while
return 0 ;
}