蓝桥杯 方格填数（DFS）

思路：暴力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;
}