/*例：s t o o d
h e * n o
e l s e *
* l o s t
10個單詞為：she he stood lost ones lost else do so no tell*/
#define N 4/*行*/
#define M 5/*列*/
#define K 7/*K>單詞的長度*/
#define L 10/*單詞的數量*/
int ax[N+2][M+2]={0},ay[N+2][M+2]={0},ax1[N+2][M+2]={0},ax2[N+2][M+2]={0},ay1[N+
2][M+2]={0},ay2[N+2][M+2]={0};
/*x表示橫,y表示豎;
拿例子來說,
ax如下:
-1 -1 -1 -1 -1 -1 -1
-1 5 0 0 0 0 -1
-1 2 0 -1 2 0 -1
-1 4 0 0 0 -1 -1
-1 -1 4 0 0 0 -1
-1 -1 -1 -1 -1 -1 -1
ax1如下:
-1 -1 -1 -1 -1 -1 -1
-1 5 5 5 5 5 -1
-1 2 2 -1 2 2 -1
-1 4 4 4 4 -1 -1
-1 -1 4 4 4 4 -1
-1 -1 -1 -1 -1 -1 -1
ax2如下:
-1 -1 -1 -1 -1 -1 -1
-1 1 2 3 4 5 -1
-1 1 2 -1 1 2 -1
-1 1 2 3 4 -1 -1
-1 -1 1 2 3 4 -1
-1 -1 -1 -1 -1 -1 -1
對于豎的可以類推.*/
float A[26]; /*A依次存儲26個字母在L個單詞中出現的次數*/
float Cl[K]; /*Cl依次存儲長度為1，2，……K的單詞數量*/
float weight[L];

work(int i,char a3[N+2][M+2],char word[L][K],int wl[])
{
char *po,*po3;
char a[N+2][M+2];
int i1,w,j,p,q,p1,q1,p2,q2;
if(i==L)
{printf("\n");
for(i1=1;i1<N+1;i1++)
{for(w=1;w<M+1;w++)
printf("%3c",a3[i1][w]);
printf("\n");
}
getch();
}

for(p=1;p<N+1;p++)
for(q=1;q<M+1;q++)
{if(a3[p][q]==''*'')
goto point;

if(ax[p][q]==wl[i])
{for(q1=q;q1<q+wl[i];q1++)
if(a3[p][q1]!=''\0''&&a3[p][q1]!=word[i][q1-q])
goto point1;

for(q1=q;q1<q+wl[i];q1++)
{for(i1=0;i1<L;i1++)/*在L個詞中尋找讓該格待填字母合法的單詞*/
{if(ay1[p][q1]==1)/*對豎著要求長度為一的格不檢驗*/
goto loop1;
if(wl[i1]==ay1[p][q1]&&word[i1][ay2[p][q1]-1]==word[i][q1-q])
{for(p2=p-ay2[p][q1];p2<p-ay2[p][q1]+ay1[p][q1];p2++)
if(a3[p2+1][q1]!=''\0''&&a3[p2+1][q1]!=word[i1][ay2[p2+1][q1]-1])
goto loop2;/*word[i1]不能讓該格待填字母合法,就檢查下一個單詞*/
goto loop1;/*找到了讓該格待填字母合法的單詞,就檢查下一格*/
}
loop2:;
}
if(i1==L) /*為真則表明該格沒有合法的單詞可以橫著填*/
goto point1;
loop1:;
}


for(po=a[0],po3=a3[0];po<a[0]+(N+2)*(M+2);po++,po3++)
*po=*po3; /*備份*/

for(q1=q;q1<q+wl[i];q1++)
a[p][q1]=word[i][q1-q]; /*填進去*/

work(i+1,a,word,wl);

}
point1:;
if(ay[p][q]==wl[i])
{for(p1=p;p1<p+wl[i];p1++)
if(a3[p1][q]!=''\0''&&a3[p1][q]!=word[i][p1-p])
goto point;

for(p1=p;p1<p+wl[i];p1++)
{for(i1=0;i1<L;i1++) /*在L個詞中尋找讓該格待填字母合法的單詞*/
{if(ax1[p1][q]==1) /*對橫著要求長度為一的格不檢驗*/
goto loop;
if(wl[i1]==ax1[p1][q]&&word[i1][ax2[p1][q]-1]==word[i][p1-p])
{for(q2=q-ax2[p1][q];q2<q-ax2[p1][q]+ax1[p1][q];q2++)
if(a3[p1][q2+1]!=''\0''&&a3[p1][q2+1]!=word[i1][ax2[p
1][q2+1]-1])
goto loo ;/*word[i1]不能讓該格待填字母合法,就
檢查下一個單詞*/
goto loop;/*找到了讓該格待填字母合法的單詞,就檢查下一格*
/
}
loo :;
}
if(i1==L) /*為真則表明該格沒有合法的單詞可以豎著填*/
goto point;
loop:;
}

for(po=a[0],po3=a3[0];po<a[0]+(N+2)*(M+2);po++,po3++)
*po=*po3; /*備份*/


for(p1=p;p1<p+wl[i];p1++)
a[p1][q]=word[i][p1-p];/*填進去*/

work(i+1,a,word,wl);/*填下一個單詞*/

}
point:;
}
}

main()
{char a[N+2][M+2]
/*{''\0'',''\0'',''\0'',''\0'',''\0'',''\0'',''\0'',''\0'',''\0'',''\0'',''\0'',''\0'',''\0'',''\0'',''\0''},
{''\0'',''\0'',''\0'',''\0'',''\0'',''*'',''\0'',''\0'',''\0'',''\0'',''*'',''\0'',''\0'',''\0'',''\0''},
{''\0'',''\0'',''\0'',''\0'',''\0'',''*'',''\0'',''\0'',''\0'',''\0'',''*'',''\0'',''\0'',''\0'',''\0''},
{''\0'',''\0'',''\0'',''\0'',''\0'',''*'',''\0'',''\0'',''\0'',''\0'',''*'',''\0'',''\0'',''\0'',''\0''},
{''\0'',''*'',''\0'',''\0'',''\0'',''\0'',''\0'',''\0'',''*'',''\0'',''\0'',''\0'',''\0'',''*'',''\0''},
{''\0'',''*'',''*'',''*'',''\0'',''\0'',''\0'',''*'',''\0'',''\0'',''\0'',''*'',''*'',''*'',''\0''},
{''\0'',''\0'',''\0'',''\0'',''\0'',''\0'',''*'',''\0'',''\0'',''*'',''\0'',''\0'',''\0'',''\0'',''\0''},
{''\0'',''\0'',''\0'',''\0'',''*'',''*'',''\0'',''\0'',''\0'',''*'',''*'',''\0'',''\0'',''\0'',''\0''},
{''\0'',''\0'',''\0'',''\0'',''\0'',''*'',''\0'',''\0'',''*'',''\0'',''\0'',''\0'',''\0'',''\0'',''\0''},
{''\0'',''*'',''*'',''*'',''\0'',''\0'',''\0'',''*'',''\0'',''\0'',''\0'',''*'',''*'',''*'',''\0''},
{''\0'',''*'',''\0'',''\0'',''\0'',''\0'',''*'',''\0'',''\0'',''\0'',''\0'',''\0'',''\0'',''*'',''\0''},
{''\0'',''\0'',''\0'',''\0'',''*'',''*'',''\0'',''\0'',''\0'',''*'',''\0'',''\0'',''\0'',''\0'',''\0''},
{''\0'',''\0'',''\0'',''\0'',''*'',''*'',''\0'',''\0'',''\0'',''*'',''\0'',''\0'',''\0'',''\0'',''\0''},
{''\0'',''\0'',''\0'',''\0'',''*'',''*'',''\0'',''\0'',''\0'',''*'',''\0'',''\0'',''\0'',''\0'',''\0''},
{''\0'',''\0'',''\0'',''\0'',''\0'',''\0'',''\0'',''\0'',''\0'',''\0'',''\0'',''\0'',''\0'',''\0'',''\0''}
}*/;

char word[L][K]/*={
"ACTS","PAY","ALA","MERYL","LT","PORE","DNA","MUM","WAR","SSTS",
"AG","ABLER","EAT","EAU","NATO","ELATES","AIR","UNE","AVEC","RPM",
"RIG","NEAP","ESS","NDY","ERMA",
"KEA","MDS","ARE","IAGO","ENS","NIPS","DRUM","RAT","ARMS","SLEEPY",
"SET","GAL","AO","ALLAY","MAT","URN","TOES","LUG","ENID","OVA",
"ATM","ELEGY","NEPAL","AAA","CAP","BUTANE","GNAT","OWL","EVER","EELS",
"KIDS","ATON","GET","EARL","LOVE","NEV","AGUE","LEAP","ALS","OMEGAS","RAE","SEAM"
,"TVS","ERR","CPA"}*/;

int wl[L];
int i,j,p,q,K1;

for(i=0;i<N+2;i++)
for(j=0;j<M+2;j++)
a[i][j]=''\0'';

while(1)
{scanf("%d,%d",&i,&j); /*輸入障礙的坐標*/
if(i==100) /*當輸入的第一個數為100時，結束對障礙的設定*/
break;
a[i][j]=''*'';
ax2[i][j]=ay2[i][j]=-1;
}

/*for(i=0;i<N+2;i++)
{for(j=0;j<M+2;j++)
printf("%c ",a[i][j]);
printf("\n");
} */

for(q=0;q<L;q++)
scanf("%s",word[q]); /*請用小寫輸入*/

for(p=0;p<26;p++)
for(i=0;i<L;i++)
for(j=0;j<strlen(word[i]);j++)
if(word[i][j]==p+''a'')
A[p]++;
for(p=0;p<K;p++)
for(i=0;i<L;i++)
if(strlen(word[i])==p+1)
Cl[p]++;
for(i=0;i<L;i++) /*計算每個單詞的weight */
{float j9=0;
for(p=0;p<strlen(word[i]);p++)
j9+=1/A[word[i][p]-97];
weight[i]/=Cl[strlen(word[i])-1];
weight[i]+=j9;
weight[i]*=strlen(word[i]);
printf("%7s\t%.2f%c",word[i],weight[i],(i+1)%4==0?''\n'':''\t'');
} /*計算完成*/
printf("\n");
for(i=0;i<L;i++) /*據weight，對單詞進行選擇法排序*/
for(j=i+1;j<L;j++)
{char t[K];
float t0;
if(weight[i]<weight[j])
{strcpy(t,word[i]);
strcpy(word[i],word[j]);
strcpy(word[j],t);

t0=weight[i];
weight[i]=weight[j];
weight[j]=t0;
}
} /*排序完成*/


for(i=0;i<N+2;i++) /*對四周編碼*/
{a[i][0]=a[i][M+1]=''*'';
ax2[i][0]=ax2[i][M+1]=ay2[i][0]=ay2[i][M+1]=-1;
}

for(i=0;i<M+2;i++) /*對四周編碼*/
{a[0][i]=a[N+1][i]=''*'';
ax2[0][i]=ax2[N+1][i]=ay2[0][i]=ay2[N+1][i]=-1;
}


for(i=1;i<N+1;i++)
for(j=1;j<M+1;j++)
{if(ax2[i][j]==-1)
continue;
ax2[i][j]=1;
for(K1=j;K1<M+1&&a[i][K1+1]!=''*'';K1++)
ax2[i][j]++;
}

for(j=1;j<M+1;j++)
for(i=1;i<N+1;i++)
{if(ay2[i][j]==-1)
continue;
ay2[i][j]=1;
for(K1=i;K1<N+1&&a[K1+1][j]!=''*'';K1++)
ay2[i][j]++;
}

for(i=0;i<N+2;i++)
for(j=0;j<M+2;j++)
{ax[i][j]=ax2[i][j];
ay[i][j]=ay2[i][j];
if(a[i][j]==''*'')
continue;
if(a[i][j-1]!=''*'')
ax[i][j]=0;
if(a[i-1][j]!=''*'')
ay[i][j]=0;
}
for(i=0;i<N+2;i++)
for(j=0;j<M+2;j++)
{if(ax[i][j]!=0)
ax1[i][j]=ax[i][j];
else
ax1[i][j]=ax1[i][j-1];
if(ay[i][j]!=0)
ay1[i][j]=ay[i][j];
else
ay1[i][j]=ay1[i-1][j];
}
for(i=1;i<N+1;i++)
for(j=1;j<M+1;j++)
{if(a[i][j]==''*'')
continue;
ax2[i][j]=ax1[i][j]-ax2[i][j]+1;
ay2[i][j]=ay1[i][j]-ay2[i][j]+1;
}

for(i=0;i<L;i++)
wl[i]=strlen(word[i]);

/*for(i=0;i<L;i++)
printf("%s ",word[i]);*/

work(0,a,word,wl);
}