蓝桥杯 2016 省赛方格填数（dfs）

素颜马尾好姑娘i 2024-02-17 20:33 46阅读 0赞

方格填数  
  
如下的10个格子  
\+--+--+--+  
| | | |  
\+--+--+--+--+  
| | | | |  
\+--+--+--+--+  
| | | |  
\+--+--+--+  
  
（如果显示有问题，也可以参看【图1.jpg】）  
  
填入0~9的数字。要求：连续的两个数字不能相邻。  
（左右、上下、对角都算相邻）  
  
一共有多少种可能的填数方案？  
  
请填写表示方案数目的整数。  
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

分析：dfs求解，逐个填数，因此考虑四个方向的判断，（左，左上，上，右上）

输出答案是：1580

#include<cstdio>
    #include<cstring>
    #include<cmath>
    using namespace std;
    int b[4][5];
    int vis[10];
    int tol;
    
    int check(int r,int c,int j){
    	if(r-1>=0 && !(r-1==0 && c==0) && abs(b[r-1][c]-j)==1)return 0;
    	if(c-1>=0 && !(r==0 && c-1==0) && abs(b[r][c-1]-j)==1)return 0;
    	if(r-1>=0 && c-1>=0 && !(r-1==0 && c-1==0)&& abs(b[r-1][c-1]-j)==1)return 0;
    	if(r-1>=0 && c+1<4 && abs(b[r-1][c+1]-j)==1)return 0;
    	return 1;
    }
    void dfs(int r,int c){
    	if(r==2 && c==3){
    		tol++;
    		return ;
    	}
    	for(int j=0;j<=9;j++){
    		if(!vis[j] && check(r,c,j)){
    			vis[j]=1;
    			if(c==3){
    				b[r][c]=j;
    				dfs(r+1,0);
    			}
    			else {
    				b[r][c]=j;
    				dfs(r,c+1);
    			}
    			vis[j]=0;
    		}
    	}
    }
    int main(){
    	memset(vis,0,sizeof(vis));
    	tol=0;
    	dfs(0,1);
    	
    	printf("%d\n",tol);
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，46人围观）

还没有评论，来说两句吧...

相关阅读

相关 2016 蓝桥杯省赛剪邮票（dfs+判重）

剪邮票如【图1.jpg】, 有12张连在一起的12生肖的邮票。现在你要从中剪下5张来，要求必须是连着的。（仅仅连接一个角不算相连）比如，【图2.j

淡淡的烟草味﹌/ 2024年02月17日 20:35/ 0 赞/ 50 阅读

相关蓝桥杯 2016 省赛方格填数（dfs）

方格填数如下的10个格子 \+--+--+--+ | | | | \+--+--+--+--+ | | | | | \+--+--+--+--+

素颜马尾好姑娘i/ 2024年02月17日 20:33/ 0 赞/ 47 阅读

相关 2016年第七届蓝桥杯省赛

2016年第七届蓝桥杯省赛 \[第一题：煤球数目\] \[第二题：生日蜡烛\] \[第三题：凑算式\] \[第四题：快速排序\] \[第五题：抽签\]

雨点打透心脏的1/2处/ 2022年11月06日 14:54/ 0 赞/ 253 阅读

相关 [蓝桥杯2015决赛]方格填数

题目：\[蓝桥杯2015决赛\]方格填数题目描述：在2行5列的格子中填入1到10的数字。要求：相邻的格子中的数，右边的大于左边的，下边的大于上边的。如下图

本是古典何须时尚/ 2022年10月16日 14:23/ 0 赞/ 170 阅读

相关 2016年蓝桥杯javaB省赛——压缩变换

> 压缩变换 > 小明最近在研究压缩算法。 > 他知道，压缩的时候如果能够使得数值很小，就能通过熵编码得到较高的压缩比。 > 然而，要使数值很小是一个挑战。 >

偏执的太偏执、/ 2022年07月28日 06:30/ 0 赞/ 222 阅读

相关 2016 蓝桥杯 JavaB组省赛

> 2018年4月1日，备战2018蓝桥杯省赛！ > 转载请注明出处[https://blog.csdn.net/yuanlaijike/article/details/6

- 日理万妓/ 2022年06月18日 10:43/ 0 赞/ 280 阅读

相关蓝桥杯--方格填数

方格填数如下的10个格子 +--+--+--+ | | | | \+--+--+--+--+ | | | | | \+

古城微笑少年丶/ 2022年05月28日 02:26/ 0 赞/ 168 阅读

相关 2016年第七届蓝桥杯java B组省赛试题方格填数

如下的10个格子 \+--+--+--+ | | | | \+--+--+--+--+ | | | | | \+--+--+--+--+ | | | |

深藏阁楼爱情的钟/ 2022年05月28日 00:30/ 0 赞/ 176 阅读

相关蓝桥杯方格填数

如图，如下的10个格子，填入0~9的数字。要求：连续的两个数字不能相邻。（左右、上下、对角都算相邻）一共有多少种可能的填数方案？请填写表示方案数目的

素颜马尾好姑娘i/ 2022年03月08日 13:08/ 0 赞/ 273 阅读

相关蓝桥杯方格填数（DFS）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

一时失言乱红尘/ 2021年07月16日 15:09/ 0 赞/ 376 阅读