蓝桥杯每日一题2023.11.18
题目描述
蓝桥杯大赛历届真题 - C 语言 B 组 - 蓝桥云课 (lanqiao.cn)
题目分析
本题使用搜索，将每一个格子进行初始赋值方便确定是否为相邻的数，将空出的两个格子首先当作已经填好数值为100，此时从第一个格子右边的格子开始搜索，每当格子到y == 4时就跳到下一行格子，每当到x == 3, y == 4时表示这些格子已填好数进行一次答案记录即可，注意确定数字是否合理时首先看是否使用过，再看是否有相邻的数，都合理进行递归，然后回复现场，注意是否存在越界问题。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
int ans, cnt, a[N][N], flag;
bool vis[N];
int dx[8] = {-1, 0, 1, 0, -1, 1, 1, -1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
void dfs(int x, int y)
{
if(x == 3 && y == 4)
{
ans ++;
for(int i = 1; i <= 3; i ++)
{
for(int j = 1; j <= 4; j ++)
{
//cout << a[i][j] << ' ';
}
//cout << '\n';
}
return;
}
if(y > 4)
{
x ++;
y = 1;
}
for(int i = 0; i <= 9; i ++)
{
if(!vis[i])
{
flag = 0;
for(int j = 0; j < 8; j ++)
{
int aa = x + dx[j];
int bb = y + dy[j];
if(aa >= 1 && aa <= 3 && bb >= 1 && bb <= 4 && (a[aa][bb] == i + 1 || a[aa][bb] == i - 1))flag = 1;
}
if(flag == 0)
{
a[x][y] = i;
vis[i] = true;
dfs(x, y + 1);
a[x][y] = 100;
vis[i] = false;
}
}
}
}
int main()
{
for(int i = 1; i <= 3; i ++)
{
for(int j = 1; j <= 4; j ++)
{
a[i][j] = 100;
}
}
dfs(1, 2);
cout << ans;
return 0;
}