赞
踩
51. N 皇后
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
输入:n = 4
输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释:如上图所示,4 皇后问题存在两个不同的解法。
示例 2:
输入:n = 1
输出:[["Q"]]
代码
class Solution { const int M=20; int col[20], dg[20], udg[20]; vector<vector<string> > ans; vector<string> temp; void dfs(int u,int n){ if(u==n){ ans.push_back(temp); return; } for(int i=0;i<n;i++){ if(!col[i] &&!dg[u-i+n] &&!udg[u+i]){ temp[u][i]='Q'; col[i]=1; dg[u-i+n]=1; udg[u+i]=1; dfs(u+1,n); temp[u][i]='.'; col[i]=0; dg[u-i+n]=0; udg[u+i]=0; } } } public: vector<vector<string>> solveNQueens(int n) { temp.resize(n,string(n,'.')); dfs(0,n); return ans; } };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。