题目描述
如下的10个格子
+--+--+--+ | | | | +--+--+--+--+ | | | | | +--+--+--+--+ | | | | +--+--+--+
（如果显示有问题，也可以参看【图1.jpg】）
填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）
一共有多少种可能的填数方案？
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
思路:1.全排列+枚举+判断 2.直接暴力+剪枝(头大,10个for,10个if,这题恐怕写完都抑郁了吧)
下面这种自己是新建了个二维数组,然后把全排列后的arr放到二维数组中,对其每个进行判断,模拟,写的有点冗余.
参考代码1
#include<bits/stdc++.h> using namespace std; int arr[10] = {0,1,2,3,4,5,6,7,8,9},map1[4][5],tx,ty,total; int NEXT[8][2] = { -1,0, 0,1, 1,0, 0,-1, -1,-1, -1,1, 1,1, 1,-1 }; bool check(int m,int n) {//判断 (m,n)是否满足 for(int i = 0; i<8; i++) { tx = m+NEXT[i][0]; ty = n +NEXT[i][1]; if(tx < 1 || tx > 3 || ty < 1 || ty >4) { //判断是否越界 continue; } if(abs(map1[m][n]-map1[tx][ty])==1) { return false; } } return true; } void solve() { int j,k; j = 1; k = 2; for(int i = 0; i < 10; i++) { map1[j][k++] = arr[i]; if(k > 4) { j++; k = 1; } } map1[1][1] = 1000; map1[3][4] = 1000; for(j = 1; j <= 3; j++) { //枚举二维数组中的数进行判断 for(k = 1; k <= 4; k++) { if(!check(j,k)) {//有一个不满足就结束判断. return; } } } total++; } int main() { do { solve(); } while(next_permutation(arr,arr+10)); cout<<total<<endl; return 0; }
接下来这个程序是自己在看了另外一位博文后写的,大题思路是:先进行全排列,然后依次对那十个数进行判断.判断时先转化成二维数组的坐标,获得周围八个点的坐标,然后依次是判断是否越界,不越界的情况下将其转换成一维数组中对应的坐标,比较俩个的值,但绝对值为1说明不符合,直接排除这种全排列情况.如果十个都没出现绝对值为1的情况说明这种全排列满足题意,计数器+1.
参考代码2
#include<bits/stdc++.h> using namespace std; int arr[12] = {100,0,1,2,3,4,5,6,7,8,9,100},total,x,y,tx,ty,k; int NEXT[8][2] = { -1,0, 0,1, 1,0, 0,-1, -1,-1, -1,1, 1,1, 1,-1 }; bool judge() { for(int i = 1; i <= 10; i++)//对该十个数进行判断 { x = i / 4; y = i % 4; for(int j = 0; j < 8; j++){//判断周围的点是否是相邻的. tx = x + NEXT[j][0];//获得周围点的坐标 ty = y + NEXT[j][1]; if(tx < 0 || tx >2 ||ty < 0 || ty > 3){//判断是否越界 continue; } k = 4 * tx + ty; if(abs(arr[i]-arr[k])==1){ return false; } } } return true; } int main() { do{ if(judge()){ total++; } }while(next_permutation(arr+1,arr+11)); cout<<total<<endl; return 0; }
自己更推荐使用第二种代码思路,其中还牵涉到了一维数组和二维数组坐标转换的知识,感到有点懵时可以画个图,帮助理解.
