蓝桥杯第七届 方格填数（dfs）

方格填数

如下的10个格子 +–+–+–+–+ | # | ? | ? | ? | +–+–+–+–+ | ? | ? | ? | ? | +–+–+–+–+ | ? | ? | ? | # | +–+–+–+–+

#：不能填数字；？：需要填写数字的空格 填入0~9的数字。要求：连续的两个数字不能相邻。 （左右、上下、对角都算相邻）

一共有多少种可能的填数方案？

请填写表示方案数目的整数。 注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

#include<stdio.h>int visit[10];int flag[3][4];int map[3][4];int ans=0;  void judge() { 	int dir[8][2]= {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}; 	int i,j,k,x,y; 	int valid=1; 	 	for(i=0;i<3;i++) 		for(j=0;j<4;j++) 		{ 			if(flag[i][j]==0) 				continue; 			for(k=0;k<8;k++) 			{ 				x=i+dir[k][0]; 				y=j+dir[k][1]; 				if(x < 0||x > 2||y<0||y>3||flag[x][y]==0)			 		continue;			 	if(map[i][j]-map[x][y]==1)			 		valid=0;			 }		 		 }	if(valid!=0)		ans++;	return; }  void dfs(int n) { 	int i,x,y; 	x=n/4;//获得所在行  	y=n%4;//获得所在列  	 	if(x==2&&y==3)	 	judge();	if(flag[x][y]!=0) //如果当前位置可填入数字	for(i=0;i<10;i++)	{		if(visit[i]==0)		{			visit[i]=1;			map[x][y]=i;			dfs(n+1);			visit[i]=0;		}	 } 	 else//当前位置不可填 	 	dfs(n+1);	return;  }  int main() {   	memset(map,0,sizeof(map));	memset(visit,0,sizeof(visit));	memset(flag,1,sizeof(flag)); 		flag[0][0]=0;	flag[2][3]=0;		dfs(0);	PRintf("%d/n",ans);	return 0; }