/*例：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);
}