2016蓝桥杯省赛 方格填数（简单方法）

方格填数

如下的10个格子
   +--+--+--+
   |  |  |  |
+--+--+--+--+
|  |  |  |  |
+--+--+--+--+
|  |  |  |
+--+--+--+

（如果显示有问题，也可以参看【图1.jpg】）

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

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

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

答案是1580

这一题明显是考DFS搜索，类似于经典的八皇后问题，不过可以取巧，用排列组合暴力是很简单的。

具体代码如下：

#include <iostream>
using namespace std;
int ans=0;
void swap(int *a,int *b)
{
	int *c;
	c=a;
	a=b;
	b=c;
}
int f(int a[])//判断这种排列组合是否符合题意
{
	if(a[0]-a[4]==-1||a[0]-a[4]==1)
		return 0;
	if(a[3]-a[4]==-1||a[3]-a[4]==1)
		return 0;
	if(a[5]-a[4]==-1||a[5]-a[4]==1)
		return 0;
	if(a[7]-a[4]==-1||a[7]-a[4]==1)
		return 0;
	if(a[8]-a[4]==-1||a[8]-a[4]==1)
		return 0;
	if(a[9]-a[4]==-1||a[9]-a[4]==1)
		return 0;
	if(a[1]-a[4]==-1||a[1]-a[4]==1)
		return 0;
	if(a[1]-a[5]==-1||a[1]-a[5]==1)
		return 0;
	if(a[1]-a[6]==-1||a[1]-a[6]==1)
		return 0;
	if(a[0]-a[5]==-1||a[0]-a[5]==1)
		return 0;
	if(a[2]-a[5]==-1||a[2]-a[5]==1)
		return 0;
	if(a[8]-a[5]==-1||a[8]-a[5]==1)
		return 0;
	if(a[9]-a[5]==-1||a[9]-a[5]==1)
		return 0;
	if(a[6]-a[5]==-1||a[6]-a[5]==1)
		return 0;
	if(a[6]-a[9]==-1||a[6]-a[9]==1)
		return 0;
	if(a[6]-a[2]==-1||a[6]-a[2]==1)
		return 0;
	if(a[3]-a[0]==-1||a[3]-a[0]==1)
		return 0;
	if(a[3]-a[7]==-1||a[3]-a[7]==1)
		return 0;
	if(a[8]-a[7]==-1||a[8]-a[7]==1)
		return 0;
	if(a[8]-a[3]==-1||a[8]-a[3]==1)
		return 0;
	if(a[9]-a[8]==-1||a[9]-a[8]==1)
		return 0;
	if(a[1]-a[0]==-1||a[1]-a[0]==1)
		return 0;
	if(a[1]-a[2]==-1||a[1]-a[2]==1)
		return 0;
}
void perm(int a[],int m,int len)//列举出0-9所有的组合进行判断
{
	if(m==len-1)
	{
		if(f(a))
			ans++;
		return ;
	}
	for(int i=m;i<len;i++)
	{
		swap(a[m],a[i]);
		perm(a,m+1,len);
		swap(a[m],a[i]);
	}
}
int main()
{	
	int  a[10] = {0,1,2,3,4,5,6,7,8,9};
	perm(a,0,10);
	cout<<ans<<endl;
	return 0;
}

DFS代码如下：

#include <cstdio>
#include <queue>
#include <map>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <stack>
#include <algorithm>
 
using namespace std;
const int r = 3, c = 4;
int mapp[10][10];
int numv[15];
int cou;
 
int dir[4][2] = { 0, -1, -1, -1, -1, 0, -1, 1 };
 
bool check(int x, int y, int n) {
	for (int i = 0; i < 4; i++) {
		int nx = x + dir[i][0];
		int ny = y + dir[i][1];
		if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
			//相邻的点有相邻的数字
			//还没有填过数字的格子-10 肯定不会等于当前格子0-9 +1或-1
			if (mapp[nx][ny] == n - 1 || mapp[nx][ny] == n + 1) {
				return false;
			}
		}
	}
	return true;
}
 
void dfs(int dep, int pos) {
 
	//(2,3)为缺口，结束
	if (dep == 2 && pos == 3) {
		cou++;
#if 0
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				printf("%4d", mapp[i][j]);
			}
			puts("");
		}
		puts("");
		system("pause");
#endif
		return;
	}
 
	if (pos >= c) {
		dfs(dep + 1, 0);
	}
	else {
		for (int i = 0; i <= 9; i++) {
			//这个数i没用过，并且没有越出格子
			if (!numv[i] && check(dep, pos, i)) {
				numv[i] = true;
				mapp[dep][pos] = i;
				dfs(dep, pos + 1);
				mapp[dep][pos] = -10;
				numv[i] = false;
			}
		}
	}
}
int main()
{
	//初始化为一个比较大的负数，那么在
	for (int i = 0; i <= 5; i++) {
		for (int j = 0; j <= 5; j++) {
			mapp[i][j] = -10;
		}
	}
	memset(numv, false, sizeof(numv));
	cou = 0;
	dfs(0, 1); //(0,0)为缺口，所以从(0,1)开始
	cout << cou << endl;  //1580
	return 0;
}

DFS参考自：https://blog.csdn.net/eventqueue/article/details/50955144