方格填数 全排列+你想不到的判断 【蓝桥杯真题】(c++实现)

方格填数

如下的10个格子
图1.jpg

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

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

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

我的思路

  • 将上图中九个格子拆分成一维数组cav[10],左右、上下、对角关系人为处理,比如cav[0]不能和cav[1]、cav[4]、cav[3]、cav[5]中数字相邻。
  • 两种算法:一、从0-9全排列填入数组,然后检查其中是否有不满足的条件,二、在全排列时检查不满足的条件,计算出结果输出。本题展示先全排列后判断的算法,即第一种算法。

算法展示

#include <iostream>
#include <algorithm>
using namespace std;
int cav[10]={0,1,2,3,4,5,6,7,8,9},ans = 0;
void swap(int a[],int i,int j)
{
    int st = a[i];
    a[i] = a[j];
    a[j] = st;
} 
bool check()
{
    //判断 
    return  abs(cav[0]-cav[1])==1||
            abs(cav[0]-cav[4])==1||
            abs(cav[0]-cav[3])==1||
            abs(cav[0]-cav[5])==1||
            abs(cav[1]-cav[2])==1||
            abs(cav[1]-cav[4])==1||
            abs(cav[1]-cav[5])==1||
            abs(cav[1]-cav[6])==1||
            abs(cav[2]-cav[5])==1||
            abs(cav[2]-cav[6])==1||
            abs(cav[3]-cav[4])==1||
            abs(cav[3]-cav[7])==1||
            abs(cav[3]-cav[8])==1||
            abs(cav[4]-cav[5])==1||
            abs(cav[4]-cav[7])==1||
            abs(cav[4]-cav[8])==1||
            abs(cav[4]-cav[9])==1||
            abs(cav[5]-cav[6])==1||
            abs(cav[5]-cav[8])==1||
            abs(cav[5]-cav[9])==1||
            abs(cav[6]-cav[9])==1||
            abs(cav[7]-cav[8])==1||
            abs(cav[8]-cav[9])==1?false:true;
}
void findans(int x)//将0-9全排列填入数组 
{
    if(x == 10) 
    {
        if(check())ans++;
        return;
    } 
    //全排列填入数组 
    for(int i = x;i<=9;i++)
    {
        swap(cav,i,x);
        findans(x+1);
        swap(cav,i,x);
    }         
}
int main()
{
    //查找数
    findans(0);//开始查找点     
    cout<<ans<<endl;
    return 0;
}

上文链接:抽签 递归【蓝桥杯真题】(c++实现)

评论

暂无评论