PersonalCorpus 版 (精华区)

//268034 2003-08-21 21:50:58 Accepted 1008 C++ 00:06.73 380K sino@HIT 
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "ctype.h"
#include "string.h"
#include "memory.h"

int m[5][5],x,n,p[25][4],num[25];
bool ok;

void tryit(int a, int b) 
{
    int i;
    if ((a==n)||(ok)) {
        ok=true;
        return;
    }
    for (i=0;i<x;i++) if (num[i]) {
        if (a) if (p[i][0]!=p[m[a-1][b]][2]) continue;
        if (b) if (p[i][3]!=p[m[a][b-1]][1]) continue;
        m[a][b]=i;
        num[i]--;
        tryit(a+(b+1)/n,(b+1)%n);
        num[i]++;
    }
}


int main(int argc, char* argv[])
{
#ifndef ONLINE_JUDGE
    freopen ("i","r",stdin);freopen ("o","w",stdout);
#endif

    int tot=0,i,j;

    while (1) {
        scanf("%d\n",&n);
        if (n==0) break;
        if (tot) printf("\n");

        for (i=0,x=0;i<n*n;i++) {
            scanf("%d%d%d%d\n",&p[x][0],&p[x][1],&p[x][2],&p[x][3]); num[x]=1;
            for (j=0;j<x;j++) if ((p[j][0]==p[x][0])&&(p[j][1]==p[x][1])&&(p[j][2]==p[x][2])&&(p[j][3]==p[x][3])) break;
            if (j==x) x++; else num[j]++;
        }
        ok=false;
        memset(m,0,sizeof(m));
        tryit(0,0);
        tot++;
        if (ok) printf("Game %d: Possible\n",tot); else printf("Game %d: Impossible\n",tot); 
    }
}