蓝桥杯方格填数（DFS）

一时失言乱红尘 2021-07-16 15:09 345阅读 0赞

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

思路：暴力DFS，构建一个二维数组来存放填的数，然后直接枚举判断所有的相邻方向是否是连续的数。用sum记录步数，从左往右填，填到3，7时跳到下一行即可。

Code:

#include<iostream>
    #include<memory.h>
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    
    int lst[6][6] ;
    int b[100];
    
    bool lin(int a, int b)
    { 
    	if (abs(a - b) <= 1)return true;
    	else return false;
    }
    
    int ans = 0;
    
    void dfs(int x, int y, int sum)
    { 
    	if (x == 3&&y==4)
    	{ 
    		ans++;return;
    	}
    	for (int i = 0;i <= 9;i++)
    	{ 
    		if (b[i] == 0 && !lin(lst[x - 1][y], i) && !lin(i, lst[x + 1][y]) && !lin(i, lst[x][y - 1]) && !lin(lst[x][y + 1], i) && !lin(i, lst[x + 1][y + 1]) && !lin(i, lst[x - 1][y - 1])&&!lin(i,lst[x+1][y-1])&&!lin(i,lst[x-1][y+1]))
    		{ 
    			b[i] = 1;
    			lst[x][y] = i;
    			if (sum == 3)
    			{ 
    				dfs(2, 1, 4);
    			}
    			else if (sum == 7)dfs(3, 1, 8);
    			else dfs(x, 1+y, sum + 1);	
    			b[i] = 0;
    			lst[x][y] = -9999;
    		}
    	}
    }
    
    int main()
    { 
    	memset(lst, 0x7f, sizeof(lst));
    	dfs(1, 2, 1);
    	cout << ans;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]: /images/20210716/b340501f2bad42a3aa945b8fd3e5b139.png

发表评论取消回复

表情：

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

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

相关阅读

相关蓝桥杯方格取数动态规划

> 题目描述 > 设有NN的方格图(N< =10),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。 > 某人从图的左上角的A 点(1,1)出发，可以向下

朴灿烈づ我的快乐病毒、/ 2023年08月17日 15:43/ 0 赞/ 83 阅读

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

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

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

相关方格填数

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

ゝ一世哀愁。/ 2022年09月30日 03:46/ 0 赞/ 178 阅读

相关蓝桥杯 dfs+剪枝

include <cstdio> include <cstring> using namespace std; int num[15]={0};

梦里梦外;/ 2022年05月29日 12:50/ 0 赞/ 144 阅读

相关 16蓝桥试题之方格填数

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

左手的ㄟ右手/ 2022年05月29日 04:42/ 0 赞/ 164 阅读

相关蓝桥杯--方格填数

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

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

相关 7届蓝桥杯第6题方格填数

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

古城微笑少年丶/ 2022年04月12日 07:49/ 0 赞/ 221 阅读

相关蓝桥杯方格计数

标题：方格计数如图p1.png所示，在二维平面上有无数个1x1的小方格。我们以某个小方格的一个顶点为圆心画一个半径为1000的圆。你能计算

桃扇骨/ 2022年03月15日 02:38/ 0 赞/ 207 阅读

相关蓝桥杯方格填数

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

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

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

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

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