思路:
题目给出的测试数据范围比较小, 使用回溯就可以AC, 搞的我也没有兴趣去研究高效解法了
总结:
刚开始, 本以为用棋盘问题的状态压缩 DP 就可以解决, 但做完 N-queen 才发现多个皇后并不能在同一条斜线上, 状态压缩的解法似乎就不好用了
代码:
#include#include #include using namespace std;class Solution {public: int N; vector pos; int result; bool visited[10]; bool attack(const int &row, const int &col) { for(int i = 0; i < pos.size(); i ++) { if(abs(pos[i]-col) == abs(i-row)) return true; } return false; } void dfs(const int &depth) { if( depth == N) { result += 1; } for(int i = 0; i < N; i ++) { if(visited[i] == 0 ) { if( pos.size() > 0 && attack(depth, i)) continue; visited[i] = 1; pos.push_back(i); dfs(depth+1); pos.pop_back(); visited[i] = 0; } } } int totalNQueens(int n) { pos.clear(); result=0; memset(visited, 0, sizeof(visited)); N = n; dfs(0); return result; }};int main() { Solution solution; int res = solution.totalNQueens(9); cout << res << endl; return 0;}
#include#include #include using namespace std;class Solution {public: int N; vector pos; vector > result; bool visited[10]; bool attack(const int &row, const int &col) { for(int i = 0; i < pos.size(); i ++) { if(abs(pos[i]-col) == abs(i-row)) return true; } return false; } void dfs(const int &depth) { if( depth == N) { vector temp; string str; for(int i = 0; i < N; i ++) { str.clear(); for(int j = 0; j < N; j ++) { if(pos[i] == j) str.push_back('Q'); else str.push_back('.'); } temp.push_back(str); } result.push_back(temp); } for(int i = 0; i < N; i ++) { if(visited[i] == 0 ) { if( pos.size() > 0 && attack(depth, i)) continue; visited[i] = 1; pos.push_back(i); dfs(depth+1); pos.pop_back(); visited[i] = 0; } } } vector > solveNQueens(int n) { pos.clear(); result.clear(); memset(visited, 0, sizeof(visited)); N = n; dfs(0); return result; }};