hrw2.c

acm中骨牌矩阵算法

#include <conio.h>       
#include <stdio.h>
/*定义数组：gpz-骨牌组的信息；
            gpjz-骨牌矩阵的信息，它记录了给出的要计算出组信息的矩阵；
            result-记录了结果，即骨牌矩阵对应的骨牌组信息；
            gpzh-记录还可以用的骨牌组号；*/
 int gpz[7][7],
	 gpjz[7][8]={{5,4,3,6,5,3,4,6},{0,6,0,1,2,3,1,1},{3,2,6,5,0,4,2,0},{5,3,6,2,3,2,0,6},
                 {4,0,4,1,0,0,4,1},{5,2,2,4,4,1,6,5},{5,5,3,6,1,2,3,1}},
     /*gpjz[7][8]={{6,6,2,6,5,2,4,1},{1,3,2,0,1,0,3,4},{1,3,2,4,6,6,5,4},{1,0,4,3,2,1,1,2},
                 {5,1,3,6,0,4,5,5},{5,5,4,0,2,6,0,3},{6,0,5,3,4,2,0,3}},*/ 
     result[7][8]={{-1,-1,-1,-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1,-1,-1,-1},
                   {-1,-1,-1,-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1,-1,-1,-1},
                   {-1,-1,-1,-1,-1,-1,-1,-1}},
     gpzh[28],count;
    

main()
{
 /*－－－－－－－－－－－－－－完成初始化的工作（begin）－－－－－－－－－－－－－－－－－－－－－－*/
 int i,j,k=1;  
 for(i=0;i<7;i++)   
   for(j=i;j<7;j++) 
   {
	   gpz[i][j]=k;
	  // printf("i=%d,j=%d,z=%d\n",i,j,k);
	   gpz[j][i]=k;
	   k++;
   }//初始化骨牌组的信息

 for(i=0;i<28;i++) gpzh[i]=0;  //初始化骨牌组号数组，0表示还可以使用，1表示不可以使用了
 
 count=0; //用来记录满足要求的答案的个数
 /*---------------------------完成初始化工作（end）--------------------------------------------------*/

 find(0,0); //从坐标（0，0）开始查找所有可能的解
 printf("count=%d",count);
}

find(int a,int b)
{
   int i,j,k;
   i=a;
   j=b;

   /*查找下一个可以开始放置骨牌组的位置*/
   while((i<7)&&(j<8)&&(result[i][j]!=-1))
   {
      j++;
	  if(j>7)
	  {
	     j=0;
		 i++;
	  }
   }
  // printf("next:i=%d,j=%d\n",i,j);

   /*当能够没有冲突地完成一次编号后，输出并返回该函数的调用点*/
   if(i>6)
   {
     for(i=0;i<7;i++)
	 {
	   for(j=0;j<8;j++) printf("%6d",result[i][j]);
	   printf("\n");
	 }
     count++;
	 printf("---------------------------------------------------------------------------------\n");
	 return;
   }

  /*假设该骨牌组是横放的*/
   if((j<7)&&(result[i][j+1]==-1)&&(gpzh[gpz[gpjz[i][j]][gpjz[i][j+1]]]==0))
   {  
	  k=gpz[gpjz[i][j]][gpjz[i][j+1]];
	 // printf("begin:i=%d,j=%d,key=%d,a=%d,b=%d,gpzh=%d\n",i,j,0,gpjz[i][j],gpjz[i][j+1],k);
      result[i][j]=k;
      result[i][j+1]=k;
      gpzh[k]=1;
	  find(i,j);
	  gpzh[k]=0;
	  result[i][j]=-1;
	  result[i][j+1]=-1;
   }

   /*假设该骨牌组是竖放的*/
   if((i<6)&&(result[i+1][j]==-1)&&(gpzh[gpz[gpjz[i][j]][gpjz[i+1][j]]]==0))
   {
      k=gpz[gpjz[i][j]][gpjz[i+1][j]];
	 // printf("begin:i=%d,j=%d,key=%d,a=%d,b=%d,gpzh=%d\n",i,j,1,gpjz[i][j],gpjz[i+1][j],k);
      result[i][j]=k;
      result[i+1][j]=k;
      gpzh[k]=1;
	  find(i,j);
	  gpzh[k]=0;
	  result[i][j]=-1;
	  result[i+1][j]=-1;
   }
}