一，第六届蓝桥杯C语言初赛
答案：1580
相似题目：N皇后问题
注意要枚举的是什么
#include<iostream>
#include<string.h>
using namespace std;
int a[][],vis[],dir[][]={{,-},{-,-},{-,},{-,}};
int cnt=;
int check(int x,int y,int num)
{
for(int i=;i<;i++)
{
int tx,ty;
tx=x+dir[i][];
ty=y+dir[i][];
if(tx>=&&tx<&&ty>=&&ty<)
{
if(a[tx][ty]==num-||a[tx][ty]==num+)//不相邻
return ;
}
}
return ;
} void dfs(int x,int y)
{
if(x==&&y==)
{
cnt++;
return;
}
if(y>)//当前行搜索完
dfs(x+,);
else
{
for(int i=;i<;i++)
{ if(check(x,y,i)&&!vis[i])//在棋盘上并且没有相邻/这个数字没有用过
{
a[x][y]=i;
vis[i]=;
dfs(x,y+);
a[x][y]=;//回溯
vis[i]=;
}
}
}
}
int main()
{
memset(vis,,sizeof(vis));
for(int i=;i<;i++)
{
for(int j=;j<;j++)
{
a[i][j]=;
}
}
dfs(,);
cout<<cnt<<endl;
return ;
}
二、第六届C语言蓝桥杯决赛
答案：42
题解一：模拟+暴力
//答案：42
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int main()
{
int a[],mp[][];
mp[][]=mp[][]=;//处理边界
for(int i=;i<;i++)
mp[][i]=;
for(int i=;i<;i++)
a[i]=i+;
int ans=;
do
{
if(a[]<a[]&&a[]<a[]&&a[]<a[]&&a[]<a[])
{
if(a[]<a[]&&a[]<a[]&&a[]<a[]&&a[]<a[])
{
if(a[]<a[]&&a[]<a[]&&a[]<a[]&&a[]<a[]&&a[]<a[])
ans++;
}
}
}while(next_permutation(a,a+));
cout<<ans<<endl;
//system("pause");
return ;
}
题解二：DFS（过程同上题）
#include<iostream>
#include<string>
#include<string.h>
using namespace std;
int a[][], vis[];
int cnt = ;
int check(int x, int y)
{
if(x==&&y==)//注意边界
return ;
else if(x==&&y==&&a[][]>a[][])
return ;
else if(x==&&a[x][y-]<a[x][y])
return ;
else if(x==&&a[x][y-]<a[x][y]&&a[x-][y]<a[x][y])
return ;
else
{
return ;
} } void dfs(int x, int y)
{
if (x == )//棋盘放满
{
cnt++;
return;
}
if (y > )//当前行搜索完
dfs(x + , );
else
{
for (int i = ; i <= ; i++)
{ if (vis[i]==)//这个数字没有用过，并且符合条件
{
a[x][y] = i;
vis[i] = ;
if(check(x,y))
dfs(x, y + );
vis[i] = ;//回溯
}
}
}
}
int main()
{
memset(vis, , sizeof(vis));
dfs(, );
cout << cnt << endl;
system("pause");
return ;
}