佑佑的語言

C++ 遇見皇后(八皇后問題)

有玩過西洋棋就知道,除了直的和橫的可以吃,斜的也是可以~~

皇后的能力就是吃斜的,沒限定一次走幾格,萬一和敵人的皇后在斜邊上碰面,另一方就是被吃掉的下場。

那咱們就來寫個程式,寫出共有幾種安全的可能

輸入說明 ：

輸入之資料格式，一列資料代表一筆測資。每一列中，共有三個整數，第一個整數 N(3<N<9) 表示是 NxN 大小的棋盤，第二個整數 x (0~N-1) 及第三個整數 y (0~N-1) 用來標示給定的皇后位置。每一個整數之間以空白字元分隔。測資可能有多筆，請繼續讀取到沒有資料為止。

輸出說明 ：

對於每一筆測資，如果可以把所有 N 只皇后都擺上去的話，請輸出 YES ，並在後面括號輸出所有合法的擺放方式數；如果沒辦法的話，請輸出 NO ，每一個測試範例的結果輸出一行。

範例 ：

題目來源:https://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?a=10982

程式碼:

1. #include <iostream>      
2. #include <vector>    
3. using namespace std;  
4. bool findqueen(vector<vector<bool> >& vbo, int x, int y)  
5. {  
6.     for (int c = x - 1; c >= 0; --c) if (vbo[c][y]) return true;  
7.     for (int c = x + 1; c < vbo.size(); ++c) if (vbo[c][y]) return true;  
8.     for (int c = y - 1; c >= 0; --c) if (vbo[x][c]) return true;  
9.     for (int c = y + 1; c < vbo[x].size(); ++c) if (vbo[x][c]) return true;  
10.     for (int c = x + 1, d = y + 1; c < vbo.size() && d < vbo[x].size(); ++c, ++d) if (vbo[c][d]) return true;  
11.     for (int c = x + 1, d = y - 1; c < vbo.size() && d >= 0; ++c, --d) if (vbo[c][d]) return true;  
12.     for (int c = x - 1, d = y + 1; c >= 0 && d < vbo[x].size(); --c, ++d) if (vbo[c][d]) return true;  
13.     for (int c = x - 1, d = y - 1; c >= 0 && d >= 0; --c, --d) if (vbo[c][d]) return true;  
14.     return false;  
15. }  
16. void BT(vector<vector<bool> >& vbo, int& count, int row, int special)  
17. {  
18.     if (row == vbo.size())  
19.     {  
20.         ++count;  
21.         return;  
22.     }  
23.     if (row == special)  
24.     {  
25.         BT(vbo, count, row + 1, special);  
26.         return;  
27.     }  
28.     for (int c = 0; c < vbo.size(); c++)  
29.     {  
30.         if (!findqueen(vbo, row, c))  
31.         {  
32.             vbo[row][c] = true;  
33.             BT(vbo, count, row + 1, special);  
34.             vbo[row][c] = false;  
35.         }  
36.     }  
37. }  
38. int main()  
39. {  
40.     int num;  
41.     while (cin >> num)  
42.     {  
43.         int x, y;  
44.         cin >> x >> y;  
45.         vector<vector<bool> > vbo(num, vector<bool>(num, false));  
46.         vbo[x][y] = true;  
47.         int count = 0;  
48.         BT(vbo, count, 0, x);  
49.         if (count == 0)  
50.         {  
51.             cout << "NO" << endl;  
52.         }  
53.         else  
54.         {  
55.             cout << "YES(" << count << ")" << endl;  
56.         }  
57.     }  
58.     return 0;  
59. }