zoj1008:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1008
题目意思是有一个游戏，即给出一个图，该图是由n*n个小正方形组成，每个小正方形又由4个三角形组成，要求用这n*n个小正方形拼成一个图，该图的每个小正方形的相邻的三角形的中间的数是相同的
题解：dfs从左到右边，从上到下，一个一个放，并且进行判断，是否合理，如果合理就放置，反之则回溯。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int map[][]; //记录不同行的四个三角形
int n,cur; //行数和当前的种类数（也就是有多少个不同行）
int result[]; //记录已经放置的方块的
int counts[]; //记录每一种木块的个数
bool dfs(int num,int n){
if(num==n*n)return ;//找到了就爱返回true
for(int i=;i<cur;i++){//遍历每一种方块注意这里是0~~cur-1；
if(!counts[i]) continue; //如果当前种类的方块数的数目为零，则跳过
if(num%n!=){//注意这里是处理第一列的情形：因为对于第一列，没有更左边的方块需要判断，
//所以没一行的第一个不需要与左边的方块进行判断，直接跳过，这里乜嘢可以改成几个if作为判断语句
if(map[i][]!=map[result[num-]][]) //把当前的种类的方块与上一个进行计较，因为这里的上一个一定是当前左边的额
continue;
}
if(num/n!=){//这里是处理第一行的情形，因为第一行的方块不需要与上一行进行比较，0——n-1的木块都不需要判断
if(map[i][]!=map[result[num-n]][])
continue;
}
result[num]=i; //记录本次的可行的木块种类
counts[i]--; //可行则该种类的木块数目减一
if(dfs(num+,n))//继续放第num+1块，
return ;
else
counts[i]++;//如果没有找到要恢复现场，这里很重要
}
return ;
}
int main(){
int ab=;
int t=;
while(scanf("%d",&n)&&n){
if(ab)
printf("\n");
ab=;
cur=;
memset(map,,sizeof(map));
memset(counts,,sizeof(counts)) ; //注意这里的清空处理
int a,b,c,d;
for(int i=;i<n*n;i++){
bool flag=true;
scanf("%d%d%d%d",&a,&b,&c,&d);
for(int j=;j<cur;j++){
if(map[j][]==a&&map[j][]==b&&map[j][]==c&&map[j][]==d)
{
counts[j]++;
flag=false;
break;
}
} //统计相同的木块数目
if(flag){
map[cur][]=a;
map[cur][]=b;
map[cur][]=c;
map[cur][]=d;
counts[cur]++;
cur++;
}
}
if(dfs(,n)) //注意这里是从0开始的，因为你储存map的时候的下标是从0开始的
printf("Game %d: Possible\n",t++);
else
printf("Game %d: Impossible\n",t++); } }