历年蓝桥杯省赛B组真题试题

（6） 方格填数

如下的10个格子

（如果显示有问题，也可以参看【图1.jpg】）

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

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

请填写表示方案数目的整数。

注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

题解: 1580

深搜+回溯，填完之后在判断是否可以。

#include #include

int flag[3][4]; //表示哪些可以填数 int mpt[3][4]; //填数 bool visit[10]; int ans = 0;

void init() //初始化 {

int i,j;

for(i = 0 ; i < 3 ; i ++) for(j = 0 ; j < 4 ; j ++) flag[i][j] = 1; flag[0][0] = 0; flag[2][3] = 0; }

void Solve() {

int dir[8][2] = { 0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,1,-1,-1}; int book = true;

for(int i = 0 ; i < 3 ; i ++) {

for(int j = 0 ; j < 4; j ++) {

//判断每个数周围是否满足 if(flag[i][j] == 0)continue; for( int k = 0 ; k < 8 ; k ++) {

int x,y;

x = i + dir[k][0]; y = j + dir[k][1];

if(x < 0 || x >= 3 || y < 0 || y >= 4 || flag[x][y] == 0) continue; if(abs(mpt[x][y] - mpt[i][j]) == 1) book = false; } } }

if(book) ans ++; }

void dfs(int index) {

int x,y;

x = index / 4;

y = index % 4; if( x == 3) {

Solve(); return; }

if(flag[x][y]) {

for(int i = 0 ; i < 10 ; i ++) {

if(!visit[i]) {

visit[i] = true; mpt[x][y] = i; dfs(index+1); visit[i] = false; } } } else {

dfs(index+1); } }

int main() {

init(); dfs(0);

printf(\ return 0; }

（7） 剪邮票

如【图1.jpg】, 有12张连在一起的12生肖的邮票。 现在你要从中剪下5张来，要求必须是连着的。 （仅仅连接一个角不算相连） 比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。

请你计算，一共有多少种不同的剪取方法。

请填写表示方案数目的整数。

注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。