zoj1008:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1008
题目意思是有一个游戏，即给出一个图，该图是由n*n个小正方形组成，每个小正方形又由4个三角形组成，要求用这n*n个小正方形拼成一个图，该图的每个小正方形的相邻的三角形的中间的数是相同的
题解：dfs从左到右边，从上到下，一个一个放，并且进行判断，是否合理，如果合理就放置，反之则回溯。
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 using namespace std; 6 int map[26][4]; //记录不同行的四个三角形 7 int n,cur; //行数和当前的种类数（也就是有多少个不同行） 8 int result[26]; //记录已经放置的方块的 9 int counts[26]; //记录每一种木块的个数 10 bool dfs(int num,int n){ 11 if(num==n*n)return 1;//找到了就爱返回true 12 for(int i=0;i<cur;i++){//遍历每一种方块注意这里是0~~cur-1； 13 if(!counts[i]) continue; //如果当前种类的方块数的数目为零，则跳过 14 if(num%n!=0){//注意这里是处理第一列的情形：因为对于第一列，没有更左边的方块需要判断， 15 //所以没一行的第一个不需要与左边的方块进行判断，直接跳过，这里乜嘢可以改成几个if作为判断语句 16 if(map[i][3]!=map[result[num-1]][1]) //把当前的种类的方块与上一个进行计较，因为这里的上一个一定是当前左边的额 17 continue; 18 } 19 if(num/n!=0){//这里是处理第一行的情形，因为第一行的方块不需要与上一行进行比较，0——n-1的木块都不需要判断 20 if(map[i][0]!=map[result[num-n]][2]) 21 continue; 22 } 23 result[num]=i; //记录本次的可行的木块种类 24 counts[i]--; //可行则该种类的木块数目减一 25 if(dfs(num+1,n))//继续放第num+1块， 26 return 1; 27 else 28 counts[i]++;//如果没有找到要恢复现场，这里很重要 29 } 30 return 0; 31 } 32 int main(){ 33 int ab=0; 34 int t=1; 35 while(scanf("%d",&n)&&n){ 36 if(ab) 37 printf(" "); 38 ab=1; 39 cur=0; 40 memset(map,0,sizeof(map)); 41 memset(counts,0,sizeof(counts)) ; //注意这里的清空处理 42 int a,b,c,d; 43 for(int i=0;i<n*n;i++){ 44 bool flag=true; 45 scanf("%d%d%d%d",&a,&b,&c,&d); 46 for(int j=0;j<cur;j++){ 47 if(map[j][0]==a&&map[j][1]==b&&map[j][2]==c&&map[j][3]==d) 48 { 49 counts[j]++; 50 flag=false; 51 break; 52 } 53 } //统计相同的木块数目 54 if(flag){ 55 map[cur][0]=a; 56 map[cur][1]=b; 57 map[cur][2]=c; 58 map[cur][3]=d; 59 counts[cur]++; 60 cur++; 61 } 62 } 63 if(dfs(0,n)) //注意这里是从0开始的，因为你储存map的时候的下标是从0开始的 64 printf("Game %d: Possible ",t++); 65 else 66 printf("Game %d: Impossible ",t++); 67 68 } 69 70 }