1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
//WARNING THIS CODE IS ONLY FOR MAKING TABLE #include <iostream> #include <sstream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <list> #include <stack> using namespace std; #define MAXN 120 //开小点,因为是打小表,打多少开多少 struct nodeType{ bool board[MAXN+2][MAXN+2]; int cnt; int xboundary; int yboundary; nodeType(){ memset(board, true, sizeof(board)); cnt = 0; xboundary = 0; yboundary = 0; } nodeType(decltype(board) a,int count,int yb,int xb){ memcpy(board, a, sizeof(board)); cnt = count; yboundary = yb; xboundary = xb; } }; void place_queen(int y,int x,nodeType &now){ for (int i = 1; i <= MAXN; i++) { now.board[i][x] = false; now.board[y][i] = false; } for (int i = 1; ; i++) { if (y + i > MAXN+1 || x + i > MAXN+1) { break; } now.board[y+i][x+i] = false; }for (int i = 1; ; i++) { if (y - i < 0 || x + i > MAXN+1) { break; } now.board[y-i][x+i] = false; }for (int i = 1; ; i++) { if (y + i > MAXN+1 || x - i < 0) { break; } now.board[y+i][x-i] = false; }for (int i = 1; ; i++) { if (y - i < 0 || x - i < 0) { break; } now.board[y-i][x-i] = false; } } long long res = 0; void dfs(nodeType now,int n){ if (now.cnt == n) { res++; return; } now.cnt++; for (int y = now.yboundary+1; y <= n; y++) { for (int x = 1; x <= n; x++) { if (!now.board[y][x]) { continue; }else{ nodeType tmp(now.board,now.cnt,y,x); place_queen(y, x, tmp); dfs(tmp, n); } } } } int main(){ int n = 0; while (cin >> n) { res = 0; nodeType init; dfs(init, n); cout << res << endl; } } |
C++作业不好好写的后果。。。
注意必须要用DFS来搜索,逐行搜。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <iostream> using namespace std; int res[11] = {0,1,0,0,2,10,4,40,92,352,724}; int main(){ int n; while(cin >> n && n){ cout << res[n] << endl; } return 0; } |