1008.txt

一个算法,深度搜索

#include<stdio.h>

int num[100];
int square[100][4];
int have[100];
int n,len,t;
int flag;
void find(int pos)
{

 int i;
 if(flag==1)return;
 if(pos==n*n)
 {
  flag=1;
  return;
 }

 for(i=0;i<len;i++)
 {

  if(num[i]==0)continue;

  if(pos%n!=0)
  {
   if(square[i][3]!=square[have[pos-1]][1])continue;
  }
  if(pos/n!=0)
  {
   if(square[i][0]!=square[have[pos-n]][2])continue;
  }
  have[pos]=i;
  num[i]--;
  find(pos+1);
  num[i]++;
 }
 return;
}

int main()
{
 int a,b,c,d;
 int i,j;

 t=0;


 freopen("in.txt","r",stdin);

 while(1)
 {

  scanf("%d",&n);
  if(n==0)break;
  if(t!=0)printf("\n");
  len=0;
  for(i=0;i<n*n;i++)
  {
   scanf("%d%d%d%d",&a,&b,&c,&d);

   for(j=0;j<len;j++)
   {

    if(a==square[j][0]&&b== square[j][1]&&c== square[j][2]&&d== square[j][3])
    {
     num[j]++;
     break;
    }
   }
   if(j==len)
   {
    square[j][0]=a;
    square[j][1]=b;
    square[j][2]=c;
    square[j][3]=d;
    num[len]=1;
    len++;

   }
  }
  flag=0;
  find(0);
  if(flag==1)
  {

   printf("Game %d: Possible\n",++t);
  }
  else
  {

   printf("Game %d: Impossible\n",++t);
  }

 }

 return 0;
}