蓝桥杯 方格填数

方格填数

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

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

---

答案

1580

---

解题思路

题目应该是要求0~9是不重复的。那么我想通过a[10]将0~9进行全排列，然后将值赋给二维数组m[3][4]。从而m[][]记录每个方格的数字。我只要写判断语句就行了。这里用来next_permutation()进行全排列，一般用do-while()加next_permutation()就能完成全排列，并且能在do-while语句中书写全排列要满足的条件。

---

附上代码

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<cmath>
using namespace std;
const int M=100010;
int a[M]={0};
int m[3][4]={0};
int ans=0;
int main()
{	
	bool is_noteven();
	m[0][0]=m[2][3]=20;
	for(int i=0;i<10;i++)
		a[i]=i;
	do{	
		m[0][1]=a[0];m[0][2]=a[1];m[0][3]=a[2];
		m[1][0]=a[3];m[1][1]=a[4];m[1][2]=a[5];m[1][3]=a[6];
		m[2][0]=a[7];m[2][1]=a[8];m[2][2]=a[9];
		if(is_noteven()) 
			ans++;
	}while(next_permutation(a,a+10));
	cout<<ans<<endl;
	return 0;
}
bool is_noteven()
{
	for(int i=0;i<3;i++)
	{
		for(int j=0;j<4;j++)
		{
			int aij=m[i][j];
			if(i-1>=0&&j-1>=0&&j+1<=3)
			{
				if(abs(aij-m[i-1][j]==1))
					return false;
				if(j-1>=0)
				{
					if(abs(aij-m[i-1][j-1])==1)
						return false;
				}
				if(j+1<=3)
				{
					if(abs(aij-m[i-1][j+1])==1)
						return false;
				}
			}
			if(i+1<=2)
			{
				if(j-1>=0) 
				{
					if(fabs(aij-m[i+1][j-1])==1)
						return false;
				}
				if(j+1<=3)
				{
					if(fabs(aij-m[i+1][j+1])==1)
						return false;
				}
				if(fabs(aij-m[i+1][j])==1)
					return false;
			}
			if(j-1>=0)
			{
				if(fabs(aij-m[i][j-1])==1)
					return false;
			}
			if(j+1<=3)
			{
				if(fabs(aij-m[i][j+1])==1)
					return false;
			}

		}
	}
	return true;
}