posted on 2021-01-11 18:20:37 | under 题解 | source
前言
这道题与八皇后很像，可以做完八皇后再来做这道题。如果你 \(\color{white}\colorbox{red}{WA}\) 了，请检查你有没有换行，有没有混淆大小写。
题意简述
一个 \(8\times 8\) 的棋盘，要摆 \(8\) 个皇后，要求每位皇后所在的 \(2\) 条直线和 \(2\) 条斜线上不能摆另一个皇后。现在已经摆了 \(3\) 个，如果有解，输出解，否则输出No Answer。
思路
很明显，这是一道dfs的题目，我们要一行行的dfs。
我们开 \(4\) 个bool数组 \(fh,fl,fzx,fyx\) （行、列、左斜、右斜），对于点 \((x,y)\) 来说，它占领了第 \(fh_x\) 行，第 \(fl_y\) 列，第 \(fzx_{x+y-1}\) 条左斜线，第 \(fyx_{x-y+8}\) 条右斜线。这个稍微画个图推个规律就能知道。如果fh[x]||fl[y]||fzx[x+y-1]||fyx[x-y+8]为真，说明这个格子摆不了皇后了，继续枚举下一个点。
注意，如果这一行已经摆了皇后了，直接搜下一行，这一行就不用管了。
无解有 \(2\) 种情况：
- 输入的棋盘上有两个同一条直线或斜线上的皇后。
dfs搜不到解。
对于情况一，我们只需在输入时判断就可以了；对于情况二，可以在dfs结束但无输出时输出。
更多的细节请看代码。
完整代码
#include <cstdio>
#include <cstdlib>
using namespace std;
#define S 20//开到2*8-1+1=16就够了，为了保险开大点
int n=8;//用n代替8，如果扩大棋盘大小，改变n一样能运行
bool a[S][S],fh[S],fl[S],fzx[S],fyx[S];//a数组记录棋盘情况
void input(){//输入
char ipt[S];
bool flag=0;
for(int i=1;i<=n;i++){
scanf("%s",ipt+1);//ipt+1能让字符串下标从1开始，老技巧了
for(int j=1;j<=n;j++){
if(ipt[j]=='Q'){
if(a[i][j]||fh[i]||fl[j]||fzx[i+j-1]||fyx[i-j+n])//可以不判断a[i][j]，但为了代码的整齐，还是加一下
flag=1;//为防止没读完数据RE的情况，我们用flag标记
a[i][j]=fh[i]=fl[j]=fzx[i+j-1]=fyx[i-j+n]=1;//标记这个皇后占领的地方
}//不用判断是'.'的情况，它又不会改变什么东西
}
}
if(flag) puts("No Answer"),exit(0);//输入就错了，无解
}
void output(){//输出
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
if(a[i][j]) putchar('Q');//putchar比printf快
else putchar('.');
puts("");//puts自带换行
}
exit(0);//数据保证唯一解或无解，输出完一个解就能走人了
}
void dfs(int x){//dfs本体
if(x==n+1) output();//搜到第9行，说明有解，输出
else if(fh[x]) dfs(x+1);//这一行有皇后，直接下一行
else{
for(int y=1;y<=n;y++){//枚举这一行的格子
if(a[x][y]||fh[x]||fl[y]||fzx[x+y-1]||fyx[x-y+n]) continue;//这个点被占领就跳过
a[x][y]=fh[x]=fl[y]=fzx[x+y-1]=fyx[x-y+n]=1;
dfs(x+1);//下一行
a[x][y]=fh[x]=fl[y]=fzx[x+y-1]=fyx[x-y+n]=0;//回溯
}
}
}
int main(){//极简主函数
input();
dfs(1);
puts("No Answer");//如果没调用到output就说明无解
return 0;
}