/*
有一个含有10个格子的图形，现用0~9填充，连续的数不能填充在相邻的格子中（包括对角线相邻）。
现每个数只能填写一次，问有多少种填充方法？
0111
1111
1110
（1表示有格子，0表示没格子） 解题思想：深度优先遍历即可
*/ #include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std; int t; //t用于存放已经填写了的格子数目
int flag[]; //记录数字是否选
int map[][]; //格子表
int sum=; //sum为可行解的数目 int judge()//判断已经填好的表是否符合要求
{
int i,j;
for(i=;i<;i++)
{
for(j=;j<;j++)
if(abs(map[i][j]-map[i][j+])==/*左右*/||abs(map[i][j]-map[i+][j])==/*上下*/||abs(map[i][j]-map[i+][j-])==/*左上角*/||abs(map[i][j]-map[i+][j+])/*右上角*/==)
return ;
}
return ;
} //dfs函数用于填表
void dfs(int t)
{
int i;
if(t==)//t=11,即此时表中的10个格子全部填了数
{
if(judge()) sum++;
return;
}
for(i=;i<=;i++)
{
if(!flag[i])
{
flag[i]=;
map[t/][t%]=i;
dfs(t+);
flag[i]=; //若递归返回，则说明该解不可行。回溯思想。
}
}
} int main()
{
int i;
for(i=;i<;i++)
{
map[i][]=;
}
memset(flag,,sizeof(flag)); //记号表归零
for(i=;i<;i++)
map[][i]=; //画表格图
map[][]=map[][]=;
dfs();
printf("%d\n",sum);
return ;
}
tz@COI HZAU
2018/3/15