蓝桥杯真题 16省6-方格填数填入0~9的数字。要求：连续的两个数字不能相邻。（左右、上下、对角都算相邻）一共有多少种可能的填数方案？请输出表示方案数目的整数。注意：你输出的应该是一

清疚 2022-12-11 05:27 195阅读 0赞

## 问题描述 ##

如下的10个格子
       +--+--+--+
       |  |  |  |
    +--+--+--+--+
    |  |  |  |  |
    +--+--+--+--+
    |  |  |  |
    +--+--+--+
    
    （如果显示有问题，也可以参看【图1.jpg】）

![在这里插入图片描述][20200928185503116.png_pic_center]

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

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

请输出表示方案数目的整数。  
注意：你输出的应该是一个整数，不要输出任何多余的内容或说明性文字。  
**输入**

没有输入。  
**输出**

输出一个整数，即可能的填数方案数。  
**题目限制**

1s, 1024KiB for each test case.  
**提示**

用printf或和cout输出答案。

## 思路： ##

又是一个典型全排列题！emmm最近小编在整理这一类题，所以都是排列组合的题（嘻嘻~）这道题依然是生成全排列，然后依次判断是否符合题目的要求就行了。有两种方法，一种是一个一个的判断，用一个if语句，当时写出来的时候感觉心态都崩了，代码见下。但好在也是对的。后来问了老师，原来可以找规律用循环写，我瞬间感觉自己是个笨b。T\_T

代码如下：（第一个方法，无脑判断）

#include <stdio.h>
    #include <algorithm>
    
    using namespace std;
    int num = 0;
    void disp(int *a)
    { 
    	if(((a[0]-a[1]!=1)&&(a[0]-a[1]!=1)&&(a[0]-a[3]!=1)&&(a[0]-a[4]!=1)&&(a[0]-a[5]!=1))&&((a[1]-a[0]!=1)&&(a[1]-a[4]!=1)&&(a[1]-a[5]!=1)&&(a[1]-a[6]!=1)&&(a[1]-a[2]!=1))&&((a[2]-a[1]!=1)&&(a[2]-a[5]!=1)&&(a[2]-a[6]!=1))&&((a[3]-a[7]!=1)&&(a[3]-a[8]!=1)&&(a[3]-a[4]!=1)&&(a[3]-a[0]!=1))&&((a[4]-a[3]!=1)&&(a[4]-a[7]!=1)&&(a[4]-a[8]!=1)&&(a[4]-a[9]!=1)&&(a[4]-a[5]!=1)&&(a[4]-a[1]!=1)&&(a[4]-a[0]!=1))&&((a[5]-a[0]!=1)&&(a[5]-a[4]!=1)&&(a[5]-a[8]!=1)&&(a[5]-a[9]!=1)&&(a[5]-a[6]!=1)&&(a[5]-a[2]!=1)&&(a[5]-a[1]!=1))&&((a[6]-a[1]!=1)&&(a[6]-a[5]!=1)&&(a[6]-a[9]!=1)&&(a[6]-a[2]!=1))&&((a[7]-a[3]!=1)&&(a[7]-a[4]!=1)&&(a[7]-a[8]!=1))&&((a[8]-a[3]!=1)&&(a[8]-a[4]!=1)&&(a[8]-a[5]!=1)&&(a[8]-a[7]!=1)&&(a[8]-a[9]!=1))&&((a[9]-a[4]!=1)&&(a[9]-a[5]!=1)&&(a[9]-a[6]!=1)&&(a[9]-a[8]!=1)))
            num++;
    }
    
    int main()
    { 
    	int n=10;
    	int a[]={ 0,1,2,3,4,5,6,7,8,9};
    	
    	do 
    	{ 
    		disp(a);
    	} while (next_permutation(a,a+n));
    	
    	printf("%d",num);
    	return 0;
    }

在小编的编辑页面可以看到有这么多T\_T但功能是好的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MjgxODA3_size_16_color_FFFFFF_t_70_pic_center]  
（第二种方法就很简单了，分别从4个方向判断就行了）  
分别是：左右检测 上下检测 左斜检测 右斜检测。

#include <stdio.h>
    #include <algorithm>
    #include <math.h>
    
    using namespace std;
    int num = 0;
    /* 用四个循环 左右检测 上下检测 左斜检测 右斜检测==1的话返回0 在主函数里面if检测 上面四个循环的返回值 */ 
    int disp (int *a,int n)
    { 
    	int i;
    	
    	for(i=0;i<9;i++)
    	{ 
    		if(abs(a[i]-a[i+1])==1 && i!=2 && i!=6 )
    			return 0;
    	}
    	for(i=0;i<6;i++)
    	{ 
    		if(abs(a[i]-a[i+4])==1)
    			return 0;
    	}
    	for(i=0;i<7;i++)
    	{ 
    		if(abs(a[i]-a[i+3])==1 && i!=3)
    			return 0;
    	}
    	for(i=0;i<5;i++)
    	{ 
    		if(abs(a[i]-a[i+5])==1 && i!=2)
    			return 0;
    	}
    	return 1;
    } 
     
    int main()
    { 
    	int a[]={ 0,1,2,3,4,5,6,7,8,9};
    	int n=10;
    	do
    	{ 
    		if(disp(a,n)==1)
    		{ 
    			num++;
    		}
    	}while(next_permutation(a,a+n));
    	printf("%d",num);
    	return 0; 
    }

[20200928185503116.png_pic_center]: /images/20221123/daa8ee20f81b43e69b13ae10e1246f6d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MjgxODA3_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/431b88fa6ad845a38b9072633888acd7.png