1008.txt

浙大acm题答案,希望可以对学习ａｃｍ的朋友有所帮助

#include<stdio.h>
#define N 26
int in[N][4],i,j,k,a[N],n,si[N];
int f(int m)
{
/*	printf("m:%d ",m);*/
	if(m>=n*n)return 1;
	else
	{
		int i1;
		for(i1=0;i1<k;i1++)
		{
			a[m]=i1;
			if(si[i1]==0)continue;
		/*	if(m==0);
			else if(m/n==0)
			{if(in[i1][3]!=in[a[m-1]][1])continue;}
			else if(m%n==0)
			{if(in[i1][0]!=in[a[m-n]][2])continue;}
			else if(in[i1][3]!=in[a[i1-1]][1]||in[i1][0]!=in[a[m-n]][2])
				continue;*/
			if(m%n!=0)
				if(in[a[m]][3]!=in[a[m-1]][1])continue;
			if(m/n!=0)
				if(in[a[m]][0]!=in[a[m-n]][2])continue;
			si[i1]--;
			
			if(f(m+1)) return 1;
			si[i1]++;
		}
	}
	return 0;
}
int main()
{
	int mn=0;
	scanf("%d",&n);
	while(n!=0)
	{
		mn++;
		for(i=0;i<n*n;i++)si[i]=0;
		for(i=0,k=0;i<n*n;i++,k++)
		{
			scanf("%d %d %d %d",&in[k][0],&in[k][1],&in[k][2],&in[k][3]);
			si[k]++;
			for(j=0;j<k;j++)
				if(in[j][0]==in[k][0]&&in[j][1]==in[k][1]&&in[j][2]==in[k][2]&&in[j][3]==in[k][3])
				{si[j]++;si[k]--;k--;break;}
		}

	/*	for(i=0;i<k;i++)
			printf("%d %d %d %d geshu: %d\n",in[i][0],in[i][1],in[i][2],in[i][3],si[i]);*/
if(mn>1)printf("\n");
		if(f(0))printf("Game %d: Possible\n",mn);
		else printf("Game %d: Impossible\n",mn);
		scanf("%d",&n);
	}
	return 0;
}













#include <stdio.h> 

int g=0;         //Game index 
int n=0;         //Puzzle size 
int q=0;         //How many different types of squares 
int square[25][4];   //Source squares 
int count[25];      //Quantity of a certain type of squares 
int table[25];      //Solution 

int place(int pos) 
{ 
   int i; 

   if(pos==n*n) 
      return 1; 

   for(i=0; i<q; i++) 
   { 
      if(count[i]==0) 
         continue; 

      if(pos%n!=0) 
         if(square[table[pos-1]][1]!=square[i][3]) 
            continue; 

      if(pos/n!=0) 
         if(square[table[pos-n]][2]!=square[i][0]) 
            continue; 

      table[pos]=i; 

      count[i]--; 

      if(place(pos+1)==1) 
         return 1; 

      count[i]++; 
   } 

   return 0; 
} 

int main() 
{ 
   int i, j; 
   int t, r, b, l;   //Temporary variables for input (top, right, bottom, left) 

   g=0; 
   q=0; 

   while(1) 
   { 
      g++; 

      scanf("%d", &n); 

      if(n==0) 
         break; 

      q=0; 

      for(i=0; i<n*n; i++) 
      { 
         scanf("%d %d %d %d", &t, &r, &b, &l); 

         j=0; 

         while(j<q) 
         { 
            if(square[j][0]==t && square[j][1]==r && square[j][2]==b && square[j][3]==l) 
            { 
               count[j]++; 
               break; 
            } 

            j++; 
         } 

         if(j==q) 
         { 
            square[j][0]=t; 
            square[j][1]=r; 
            square[j][2]=b; 
            square[j][3]=l; 

            count[j]=1; 

            q++; 
         } 
      } 

      if(g>1) 
         printf("\n"); 
      if(place(0)==1) 
         printf("Game %d: Possible\n", g); 
      else 
         printf("Game %d: Impossible\n", g); 
   } 

   return 0; 
}