P1219 [USACO1.5]八皇后 Checker Challenge 题解
难度：⭐⭐
知识点：DFS
题目链接
序言：
题目说实话不难，一道黄题但是WA了2次，这道题对我还是有其探究的价值的。
1. 入手程序
经典的八皇后问题加上了对角线的限制，其基本的深度优先搜索思想不变，其关键点主要是book数组的改变，用一个函数 bj() 来单独处理，观察对于任意一点进行选择，不能选择的点有：
对此，我们将book数组扩展为两个，book1[i][j]负责标记选定点[i][j]后不能选择的点中的对角线部分，book2负责横排和竖排。
再来设计DFS的逻辑，这里采用的是对于每一个横排进行搜索，竖排同理。
同时我们还能将book2[i][j]优化为book2[i]:由于是对一横排进行整体处理，所以可以规避掉横排重复的情况。
至此，代码基本结构已经清晰。
初版代码如下：
#include<bits/stdc++.h>
using namespace std;
int n,ans;
bool book[15][15];
int zf[15];
bool book2[15];
void bj(int x,int y,bool b)
{
for(int i=x,j=y;i<=n && j>=1;i++,j--)
book[i][j]=b;
for(int i=x,j=y;i<=n && j<=n;i++,j++)
book[i][j]=b;
for(int i=x,j=y;i>=1 && j>=1;i--,j--)
book[i][j]=b;
for(int i=x,j=y;i>=1 && j<=n;i--,j++)
book[i][j]=b;
return;
}
void dfs(int h)
{
if(h==n+1)
{
ans++;
if(ans<=3)
{
for(int i=1;i<=n;i++)
printf("%d ",zf[i]);
printf("\n");
}
return;
}
for(int i=1;i<=n;i++)
if(book[h][i]==0 && book2[i]==0)
{
bj(h,i,1);
zf[h]=i;
book2[i]=1;
dfs(h+1);
book2[i]=0;
bj(h,i,0);
}
return;
}
int main()
{
scanf("%d",&n);
dfs(1);
printf("%d",ans);
return 0;
}
2.编程思路
测试样例我们便可以发现问题，程序输出的结果远大于实际。
在手动模拟后，我们可以发现原因所在，如下图（样例数据）时：
程序发现无法选出最后一个点，回溯，在回溯前清空了标记：
然而这也同时覆盖了其他选点所导致的不能选的点
我们要修改bj()函数，改为：
void bj(int x,int y,int b)
{
for(int i=x,j=y;i<=n && j>=1;i++,j--)
book[i][j]+=b;
for(int i=x,j=y;i<=n && j<=n;i++,j++)
book[i][j]+=b;
for(int i=x,j=y;i>=1 && j>=1;i--,j--)
book[i][j]+=b;
for(int i=x,j=y;i>=1 && j<=n;i--,j++)
book[i][j]+=b;
return;
}
在打标记时b参数传入1，清除时传入0
这样就解决啦~
3.代码实现
#include<bits/stdc++.h>
using namespace std;
int n,ans;
int book[15][15];
int zf[15];
bool book2[15];
void bj(int x,int y,int b)
{
for(int i=x,j=y;i<=n && j>=1;i++,j--)
book[i][j]+=b;
for(int i=x,j=y;i<=n && j<=n;i++,j++)
book[i][j]+=b;
for(int i=x,j=y;i>=1 && j>=1;i--,j--)
book[i][j]+=b;
for(int i=x,j=y;i>=1 && j<=n;i--,j++)
book[i][j]+=b;
return;
}
void dfs(int h)
{
if(h==n+1)
{
ans++;
if(ans<=3)
{
for(int i=1;i<=n;i++)
printf("%d ",zf[i]);
printf("\n");
}
return;
}
for(int i=1;i<=n;i++)
if(book[h][i]==0 && book2[i]==0)
{
bj(h,i,1);
zf[h]=i;
book2[i]=1;
dfs(h+1);
book2[i]=0;
bj(h,i,-1);
}
return;
}
int main()
{
scanf("%d",&n);
dfs(1);
printf("%d",ans);
return 0;
}
