当前位置 博文首页 > pzjdsg666的博客：【枚举】方格填数
题目描述
如图所示形状的八个方格中填入1-8这八个数字，使得相邻的和对角线上的数字之差不为1，编程求解按照方格顺序从小到大排序后的第k种填法方案。?
?
输入格式
1个整数K，保证有合法输出结果。
输出格式
第k种方案按照方格编号从小到大的顺序输出，中间有1个空格间隔。?
样例
样例输入
1
样例输出
2 5 8 6 3 1 4 7
数据范围与提示
注意对角线要考虑b1和b2，b4之间，b8和b4，b7之间的关系
典型的枚举算法，题目已经提示了您
#include<bits/stdc++.h>//万能头
/*等价于:
#include<algorithm>
#include<iostream>
#include<cmath>*/
using namespace std;//申请标准命名空间
int a[4][8],sum=1,o;//定义变量,o用于输入，sum用于计数求和
void perm(int list[], int k, int m)//用递归算法来计算
{
if(k==m)
{
if(abs(list[1]-list[4])!=1&&abs(list[0]-list[2])!=1&&abs(list[2]-list[5])!=1&&abs(list[5]-list[7])!=1&&abs(list[3]-list[6])!=1&&abs(list[1]-list[2])!=1&&abs(list[2]-list[3])!=1&&abs(list[4]-list[5])!=1&&abs(list[5]-list[6])!=1&&abs(list[0]-list[1])!=1&&abs(list[0]-list[3])!=1&&abs(list[1]-list[5])!=1&&abs(list[2]-list[4])!=1&&abs(list[2]-list[6])!=1&&abs(list[3]-list[5])!=1&&abs(list[4]-list[7])!=1&&abs(list[6]-list[7])!=1)//abs取绝对值函数，在cmath库，但都适用了万能头，就可以不管了（呵呵~）
//此处用abs的原因是：你并不知道前减后的结果是正是负，所以不加abs就漏掉了-1的情况
{
if(o==sum)//已经求出结果，输出答案（无需解释~）
for(int i=0;i<=m;i++)
cout<<list[i]<<" ";
sum++;
}
}
else
for (int i=k; i <= m;i++)
{
swap(list[k],list[i]);
perm(list, k+1,m);//递归算法，没有就继续枚举下一个
//此处每次k++,不会重复算多次解（算了多此一举~）
swap(list[k],list[i]);//swap:交换函数，在algorithm库中
}
}
//注意：穷举可能会超时，还会输出类似于“1 2 3 4 6 5 7 8”之类的奇葩（嘤嘤嘤~）
int main()
{
int s[]={1,2,3,4,5,6,7,8};//别忘记附初值,如果不赋值，就必须加数组下标
cin>>o;//输入
perm(s, 0, 7);//计算
return 0;//完美收官，养成好习惯
}
//总结：本来可以不用函数，但用了函数思路更清晰，检查更方便！