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