暑假集训每日一题0717（DFS）

这题是ZOJ 1008那题。

给你n*n个方块，每个方块被对角线划分为4部分，每一部分里面有一个数字，问能否将方块拼成一个边长为n的大方块，使得相邻方块的相邻数字相同。

用dfs搜索，需要剪枝，同一层中相同方块只搜索一次。

#include <stdio.h>
#include <string.h>
#define N 26
#define T 0
#define R 1
#define B 2
#define L 3
int x[N][4],top;
int n,id[N],num[N];
bool success;
int Left(int k)
{
    if(k%n==0)  return -1;
    return k-1;
}
int Top(int k)
{
    if(k/n==0)  return -1;
    return k-n;
}
void dfs(int cnt)
{
    int i;
    if(cnt==n*n)
    {
        success=true;
        return;
    }
    for(i=0;i<top && !success;i++)
    {
        if(num[i]==0)  continue;
        if(Left(cnt)!=-1 && x[id[Left(cnt)]][R]!=x[i][L])  continue;
        if(Top(cnt)!=-1 && x[id[Top(cnt)]][B]!=x[i][T])   continue;
        id[cnt]=i;
        num[i]--;
        dfs(cnt+1);
        num[i]++;
    }
}
int main()
{
    int kase=0;
    int i,j;
    int a,b,c,d;
    while(scanf("%d",&n)&&n)
    {
        top=0;
        memset(num,0,sizeof(num));
        for(i=0;i<n*n;i++)
        {
            scanf("%d%d%d%d",&a,&b,&c,&d);
            for(j=0;j<top;j++)
            {
                if(x[j][0]==a && x[j][1]==b && x[j][2]==c && x[j][3]==d)    break;
            }
            num[j]++;
            if(j==top)
            {
                x[j][0]=a;
                x[j][1]=b;
                x[j][2]=c;
                x[j][3]=d;
                top++;
            }
        }
        success=false;
        dfs(0);
        if(kase)    puts("");
        printf("Game %d: ",++kase);
        if(success) puts("Possible");
        else    puts("Impossible");
    }
    return 0;
}