運行結果
代碼如下
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int MAX = 1024; 4 const char *LINE32 = "--------------------------------"; 5 const bool PRINT_DETAILS = false; 6 long long n, cnt = 0;// n表示皇后數量，cnt表示方案數量 7 int vis[3][2*MAX+1]; 8 //v[0][]、v[1][]、v[2][]分別表示列、主對角線、副對角線是否存在皇后 9 // 為0時表示無皇后，非0則表示有，且v[0][4]=2表示第四列第二行存在皇后 10 11 void print() { 12 cout << LINE32 << endl; 13 cout << "第" << cnt << "個方案: " << endl; 14 for (int i = 1; i <= n; i++) { 15 if (i != 1) { 16 cout << ", "; 17 } 18 cout << "(" << vis[0][i] << "," << i << ")"; 19 } 20 cout << endl; 21 for (int i = 1; i <= n; i++) { 22 for (int j = 1; j <= n; j++) { 23 if (vis[0][j] != i) { 24 cout << 'x'; 25 } else { 26 cout << 'Q'; 27 } 28 } 29 cout << endl; 30 } 31 } 32 33 bool check(int row, int col) {// 檢查是否可以在（row，col）這個坐標放置皇后 34 return !(vis[0][col] || vis[1][row-col+n] || vis[2][row+col]); 35 } 36 void place(int x, int y, int *r2c) {// 在（x，y）的位置上放置皇后 37 vis[0][y] = x; 38 vis[1][x-y+n] = vis[2][x+y] = 1; 39 r2c[x] = y; 40 } 41 void remove(int x, int y) {// 移除（x，y）位置上的皇后 42 vis[0][y] = vis[1][x-y+n] = vis[2][x+y] = 0; 43 } 44 void solve(int n) {// 與非遞回實作1的不同點在于，A.使用了vis[3][]加快了判斷，B.回溯的具體操作是在vis[3][]上而不是r2c[]上 45 int r2c[n+5];// 存放各行所放位置的列數，其實類似于遞回實作1和非遞回實作1中使用的queen[] 46 r2c[0] = 0;// 這里要初始化，否則最后要退出下面的回圈時會陣列越界，受影響的代碼是63_42 47 int row = 1, col = 1; 48 place(row, col, r2c); 49 row = 2;//在（1，1）的位置上放置一個皇后，然后進入回圈，開始尋找第二行放置的位置 50 while (row > 0) {// row的值最后為0，因為所有情況都檢查完時，第一行往上回溯，row值就為0 51 if (row > n) { 52 // 找到一個解，之后需要向上回溯：移除上一行的皇后，從上一行的下一列嘗試放置皇后 53 cnt++; 54 if (PRINT_DETAILS) { 55 print(); 56 } 57 row--;// row回傳上一行 58 remove(row, r2c[row]);// 移除上一行中的皇后 59 col = r2c[row]+1;// 此時的（row，col）為下一次嘗試放置的位置 60 } else if (col > n) { 61 // 當前row行中的每一個位置都嘗試并放置了，回溯 62 row--; 63 remove(row, r2c[row]); 64 col = r2c[row]+1; 65 } else if (check(row, col)) { 66 // 找到一個符合的位置 67 place(row, col, r2c);// 放置皇后 68 row++;// 查找下一行放置的位置 69 col = 1;// 并且是從第一列開始放置 70 } else { 71 // 這一列不符合，查找下一列 72 col++; 73 } 74 } 75 } 76 77 int main() { 78 // input 79 cout << "輸入皇后個數: "; 80 cin >> n; 81 // compute 82 clock_t begin = clock(); 83 solve(n); 84 clock_t end = clock(); 85 // output 86 cout << LINE32 << endl; 87 cout << n << "皇后問題一共有" << cnt << "種解決方案" << endl; 88 cout << LINE32 << endl; 89 cout << "回溯非遞回演算法實作2 解決" << n << "皇后問題耗時" << /*end-begin << "打點" <<*/(double)(end-begin)/CLOCKS_PER_SEC << "s" << endl; 90 return 0; 91 } 92 // 14 3~5s
與回溯遞回演算法實作2對比
回溯遞回演算法實作2運行情況
回溯非遞回演算法實作2運行情況
非遞回實作還是比遞回實作慢一點，有點不符合預期，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/199363.html
標籤：其他
下一篇：第11屆藍橋杯省賽模擬 螺旋矩陣