【題目連結】
ybt 1214：八皇後
OpenJudge NOI 2.5 1756:八皇後
【題目考點】
1. 深搜
2. 二維數組
同一行：行坐标相同
同一列：列坐标相同
同一左上右下斜線：行列坐标內插補點相同
同一右上左下斜線：行列坐标加和相同
【解題思路】
每個皇後會占用它所在的行、列及兩條斜線。是以自然一行中隻能放一個皇後。
本題關鍵是如何表示對豎線及斜線的占用
設數組
vis_c
，
vis_c[i]
表示第i列是否已被占用。
對于斜線被占用的情況：
對于一個8行8列的矩陣，其左上右下斜線數量有15條，行坐标減縱坐标內插補點最小為-7，最大為7。将這個數字加上8後，數字範圍為1~15，可以對應第1條斜線，第2條斜線，…，第15條斜線。
設數組
vis_r
，
vis_r[x-y+8]
表示(x,y)所在的左上右下斜線是否已被占用
對于一個8行8列的矩陣，其右上左下斜線數量有15條，行坐标與列坐标加和最小為2，最大為16。将這個數字減1後，數字範圍為1~15，可以對應第1條斜線，第2條斜線，…，第15條斜線。
設數組
vis_l
，
vis_l[x+y-1]
表示(x,y)所在的右上左下斜線是否已被占用。
确定第x行放皇後的位置，搜尋每一列y，如果(x,y)所在的列、左上右下斜線、右上左下斜線都沒有被占用（即
vis_c[y]
，
vis_l[x+y-1]
，
vis_r[x-y+8]
都為
false
），那麼可以在(x,y)位置放皇後，更新豎線及斜線的占用狀态，接着搜尋下一行放皇後的位置。搜尋結束後注意狀态還原。
如果已經在第8行放了皇後，那麼就得到一個皇後串，此時就不用再到下一行搜尋放皇後的位置了。
至于皇後串的建構，可以用整型變量或字元串來儲存。本例使用的是整型變量。
設整型變量q儲存皇後串，末尾添加數字y，寫法為
q = q*10 + y
，去掉末尾數字，寫法為：
q /= 10
。
用整型數組res儲存所有皇後串，
res[i]
為第i個皇後串。
由于周遊的過程中，每一行都是從小到大周遊的，是以得到的皇後串一定也是從小到大按順序得到的。
搜尋過程整體完成後，即可針對每次詢問輸出對應的皇後串。
【題解代碼】
解法1：深搜
- 用整數表示皇後串
#include <bits/stdc++.h>
using namespace std;
bool vis_c[10], vis_r[16], vis_l[16];//vis_c[i]:第i列是否被占用 vis_l[i]:第i右上左下斜線是否被占用 vis_r[i]:第i左上右下斜線是否被占用
int q, res[100], r_i;//q:皇後串 res[i]:第i個皇後串 r_i:皇後串的個數
//在位置x，y設定或拿開皇後後，對列、斜線占用情況的變化
void setVis(int x, int y, bool isSet)
{
vis_c[y] = isSet;
vis_r[x-y+8] = isSet;
vis_l[x+y-1] = isSet;
}
//在第x行放皇後
void dfs(int x)
{
for(int y = 1; y <= 8; ++y)//能否在第x行第y列放皇後
{
if(vis_c[y] == false && vis_r[x-y+8] == false && vis_l[x+y-1] == false)//如果(x,y)所在的列及斜線都沒有被占用
{
q = q*10 + y;//皇後串末尾添加y
setVis(x, y, true);//設定對列和斜線的占用
if(x == 8)
res[++r_i] = q;//記錄皇後串
else
dfs(x+1);
setVis(x, y, false);//狀态還原
q /= 10;//皇後串去掉末尾數字
}
}
}
int main()
{
dfs(1);
int n, a;
cin >> n;
for(int i = 1; i <= n; ++i)
{
cin >> a;
cout << res[a] << endl;
}
return 0;
}
- 用string類對象表示皇後串
#include <bits/stdc++.h>
using namespace std;
bool vis_c[10], vis_r[16], vis_l[16];//vis_c[i]:第i列是否被占用 vis_l[i]:第i右上左下斜線是否被占用 vis_r[i]:第i左上右下斜線是否被占用
string q;//q:皇後串
vector<string> res;//res[i-1]:第i個皇後串
//在位置x，y設定或拿開皇後後，對列、斜線占用情況的變化
void setVis(int x, int y, bool isSet)
{
vis_c[y] = isSet;
vis_r[x-y+8] = isSet;
vis_l[x+y-1] = isSet;
}
//在第x行放皇後
void dfs(int x)
{
for(int y = 1; y <= 8; ++y)//能否在第x行第y列放皇後
{
if(vis_c[y] == false && vis_r[x-y+8] == false && vis_l[x+y-1] == false)//如果(x,y)所在的列及斜線都沒有被占用
{
q.push_back(char(y+'0')); //皇後串末尾添加y（轉為字元型數字）
setVis(x, y, true);//設定對列和斜線的占用
if(x == 8)
res.push_back(q);//記錄皇後串
else
dfs(x+1);
setVis(x, y, false);//狀态還原
q.pop_back();//皇後串去掉末尾數字
}
}
}
int main()
{
dfs(1);
int n, a;
cin >> n;
for(int i = 1; i <= n; ++i)
{
cin >> a;
cout << res[a-1] << endl;//a從1開始，res下标從0開始
}
return 0;
}