搜索算法也算是一種暴力枚舉策略勿负，但是其算法特性決定了效率比直接的枚舉所有答案要高眶痰，因?yàn)樗阉骺梢蕴^一些無效狀態(tài)厕诡，降低問題規(guī)模额湘。
題目來源 八皇后 Checker Challenge
使用二維數(shù)組建圖的話會(huì)增加搜索的操作描馅，占用更大的空間把夸。這里可以使用通過發(fā)現(xiàn)規(guī)律來降維的思想，具體如下
初始圖形中第一個(gè)皇后坐標(biāo)為（1铭污，2）恋日，對(duì)于其所有在主對(duì)角線平行的共線皇后為（2，3）嘹狞，（3岂膳，4），（4磅网，5）谈截，（5，6）涧偷，其規(guī)律是總有橫坐標(biāo)與縱坐標(biāo)之差為與皇后所在位置相同簸喂；同理副對(duì)角線平行的皇后所在位置都有坐標(biāo)與皇后所在位置橫縱坐標(biāo)之和相同×浅保基于此喻鳄，使用數(shù)組lx表示標(biāo)記副對(duì)角線狀態(tài)的數(shù)組，數(shù)組rx表示標(biāo)記主對(duì)角線的數(shù)組确封。則有：
lx[x+y]=1;rx[x-y]=1;
來分別表示當(dāng)前（x,y）的左斜和右斜是否有皇后除呵。但問題是x-y可能為負(fù)數(shù)，數(shù)組下標(biāo)不能為負(fù)數(shù)爪喘。這里可以使用加一個(gè)常量的方式颜曾，因?yàn)榧觽€(gè)常量相對(duì)位置不會(huì)發(fā)生變化，值得注意的是腥放，加常量之后對(duì)應(yīng)數(shù)組大小也應(yīng)該調(diào)整泛啸，否則會(huì)越界。
給出AC代碼：
#include<iostream>
using namespace std;
int col[105],lx[105],rx[105], ans[105],n,cnt=0;//col代表列，lx代表左斜候址，rx代表右斜
void print(){
if(cnt<=2){
for(int i=1;i<=n;i++)
cout<<ans[i]<<" ";
cout<<endl;
}
cnt++;
}
void dfs(int k){
if(k>n) {
print();
return;
}
else{
for(int i=1;i<=n;i++){
if(!col[i]&&!lx[k+i]&&!rx[k-i+n]){
//做占用操作
ans[k]=i;
col[i]=1;
lx[k+i]=1;
rx[k-i+n]=1;//防止出現(xiàn)負(fù)數(shù)
dfs(k+1);//下一行
//做回溯
col[i]=0;
lx[i+k]=0;
rx[k-i+n]=0;
}
}
}
}
int main(){
cin>>n;
dfs(1);
cout<<cnt<<endl;
return 0;
}
使用k來表示當(dāng)前到哪一列了吕粹，dfs（）不代表深度優(yōu)先搜索，對(duì)于搜索問題來講岗仑，dfs作函數(shù)名似乎是做題家的共識(shí)匹耕。
題解參考https://www.luogu.com.cn/blog/kiroto/solution-p1218
