問題描述 ：
如何在棋盤上擺滿彼此不會互相攻擊到的皇后，一直以來是在西洋棋盤上一個很經典也很有趣的問題。
在西洋棋中，皇后的攻擊範圍是所有棋子裡面最大的，一只皇后 (Q) 可以控制縱橫與兩條斜對角線上的所有格子，範圍如下圖深色的格子所示，
一般而言，我們在 NxN (N≥4) 以上大小的棋盤，都可以擺上 N 只皇后而不互相攻擊，範例如下所示。
如果在 NxN 的棋盤上指定一只皇后的位置，請設計程式檢查是否可以擺上剩餘的 N-1 只皇后。
輸入說明 ：
輸入之資料格式，一列資料代表一筆測資。每一列中，共有三個整數，第一個整數 N(3<N<9) 表示是 NxN 大小的棋盤，第二個整數 x (0~N-1) 及第三個整數 y (0~N-1) 用來標示給定的皇后位置。每一個整數之間以空白字元分隔。測資可能有多筆，請繼續讀取到沒有資料為止。
輸出說明 ：
對於每一筆測資，如果可以把所有 N 只皇后都擺上去的話，請輸出 YES ，並在後面括號輸出所有合法的擺放方式數；如果沒辦法的話，請輸出 NO ，每一個測試範例的結果輸出一行。
思路: 八皇后問題, 首先你必須要懂八皇后怎麼放的, 用的是回溯法, 用一個一維陣列就能記錄皇后xy位置, 因為皇后每一行只能有一個,
比如 第1行皇后在第5個位置 那麼 queen[1] = 5, 第0行皇后在第1個位置 那麼 queen[0] = 1
所以從第0行開始放, 然後第0行又可以放從0~n, 每個都放放看。
那麼怎麼樣快速判斷皇后是否在同一個垂直線或在斜線呢, 水平線已經處理完了因為是一行一行放的。
所以就用到剛剛紀錄皇后位置的陣列, 從第0行開始掃描到第k行(k是剛剛做到哪一行) 比對陣列有沒有一樣 一樣代表垂直線兩個皇后
斜線的話用斜率 = 1, 又斜率 = (y-y0)/(x-x0) , 所以就直接用 y-y0 = x - x0, 來判斷是否同一個斜線。
如果都沒有上述的狀況, 那麼就繼續坐下一行。
依此類推, 做到n個
這題題目給了一個皇后位置, 所以說那行皇后不能給他用其他位置, 也就是說遇到那行只能做1次。就是不能給那行其他皇后位置，會出錯，我之前卡在這。
程式碼:
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int queen[10];
int n, x, y, ans;
bool canPlaceQ(int k){
for(int i = 0; i < k; ++i){
if(queen[i] == queen[k] || abs(k - i) == abs(queen[i] - queen[k]))
return false;
}
return true;
}
void dfs(int k){
for(int j = 0; j < n; ++j){
if(k == x){
queen[k] = y;
j = n;
}
else
queen[k] = j;
if(k == n - 1 && canPlaceQ(k)){
ans++;
return;
}
else if(canPlaceQ(k))
dfs(k+1);
}
}
int main()
{
while(cin >> n >> x >> y){
memset(queen, 0, sizeof queen);
ans = 0;
dfs(0);
if(ans)
cout << "YES" << '(' << ans << ")\n";
else
cout << "NO\n";
}
return 0;
}
留言列表
Atcoder (1)
