leetcode 51. N 皇后

题目详情

题目链接 n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 上图为 8 皇后问题的一种解法。 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例： 输入：4 输出：[ [".Q…", // 解法 1 “…Q”, “Q…”, “…Q.”], ["…Q.", // 解法 2 “Q…”, “…Q”, “.Q…”] ] 解释: 4 皇后问题存在两个不同的解法。

提示：

皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

我的代码

class Solution { private: vector<vector<string>> results; int num; public: void placeQueen(vector<string> result, int loc) { if (loc == num) { results.push_back(result); return; } for (int i = 0; i < num; ++i) { if (result[loc][i] == ' ') { auto temp = result; temp[loc][i] = 'Q'; for (int j = 0; j < num; ++j) { if (temp[loc][j] == ' ') { temp[loc][j] = '.'; } } for (int row = loc; row < num; ++row) { if (temp[row][i] == ' ') { temp[row][i] = '.'; } } int row = loc + 1, col = i + 1; while ((row < num) && (col < num)) { temp[row++][col++] = '.'; } row = loc + 1, col = i - 1; while ((row < num) && (col >= 0)) { temp[row++][col--] = '.'; } placeQueen(temp, loc + 1); } } } vector<vector<string>> solveNQueens(int n) { num = n; placeQueen(vector<string> (n, string (n, ' ')), 0); return results; } };

我的成绩

执行结果：通过 执行用时：44 ms, 在所有 C++ 提交中击败了20.05%的用户 内存消耗：16.8 MB, 在所有 C++ 提交中击败了13.22%的用户

一些想法

本道题不是太难，只需要考虑到放置规则，递归放置即可。

执行用时为 0 ms 的范例

class Solution { public: static const int M = 20; int row[M]={0},dg[M]={0},udg[M]={0}; vector<string> a; vector<vector<string>> res; void dfs(int u,int n) { if(u==n) { res.push_back(a); } for(int i=0;i<n;i++) { if(!row[i] && !dg[u-i+n] && !udg[u+i]) { a[u][i]='Q'; row[i]=dg[u-i+n]=udg[u+i]=1; dfs(u+1,n); row[i]=dg[u-i+n]=udg[u+i]=0; a[u][i]='.'; } } } vector<vector<string>> solveNQueens(int n) { a.resize(n,string(n,'.')); dfs(0,n); return res; } };

思考

参见官方解答