首页 > 代码库 > LeetCode N-Queens
LeetCode N-Queens
又是一个八皇后问题:
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens‘ placement, where ‘Q‘
and ‘.‘
both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
[ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]
class Solution { public: vector<vector<string> > solveNQueens(int n) { this->N=n; memset(matrix,0,sizeof(matrix)); dfs(0); return d; } int check(int x,int y) { for(int j=0;j<y;++j) if(matrix[x][j]==1)return 0; for(int i=0;i<N;++i) for(int j=0;j<y;++j) { if(abs(i-x)==abs(j-y)&&matrix[i][j]==1)return 0; } return 1; } void dfs(int j) { if(j==N) { //存储 vector<string>mt; for(int i=0;i<N;++i){ string td; for(int j=0;j<N;++j) { if(matrix[i][j]==0)td+='.'; if(matrix[i][j]==1)td+='Q'; } mt.push_back(td); } d.push_back(mt); return ; } for(int i=0;i<N;++i) { if(matrix[i][j]==0&&check(i,j)) { matrix[i][j]=1; dfs(j+1); matrix[i][j]=0; } } } private : int N; vector<vector<string> > d; int matrix[100][100]; };
LeetCode N-Queens
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。