首页 > 代码库 > LeetCode: N-Queens [050]
LeetCode: N-Queens [050]
【题目】
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
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.."] ]
【题意】
解N皇后问题。在nXn的矩阵上放置n个皇后,每行放一个,其所在列和两个斜线上没有其他皇后放置。
该题要求得到所有可行解。‘Q’表示皇后,‘.‘表示空位置
【思路】
和解Sudoku Solver的方法相同,用DFS求解【代码】
class Solution { public: bool isValid(vector<string>&matrix, int x, int y, int n){ //考虑纵向 int i=0; int j=y; for(;i<n; i++){ if(i!=x && matrix[i][j]=='Q')return false; } //考虑指向左上角的斜线 i=x-1; j=y-1; while(i>=0&&j>=0){ if(matrix[i][j]=='Q')return false; i--;j--; } //考虑指向右上角的斜线 i=x-1; j=y+1; while(i>=0&&j<n){ if(matrix[i][j]=='Q')return false; i--;j++; } return true; } void dfs(vector<vector<string> >&result, vector<string>matrix, int lineNo, int n){ //matrix--已经完成部分皇后放置的二维矩阵 //lineNo--当前正在处理的行的行号,从1开始 //n--总行数,也就是皇后数 if(lineNo>n){ result.push_back(matrix); return; } for(int i=0; i<n; i++){ matrix[lineNo-1][i]='Q'; if(isValid(matrix, lineNo-1, i, n)){ dfs(result, matrix, lineNo+1, n); } matrix[lineNo-1][i]='.'; } } vector<vector<string> > solveNQueens(int n) { vector<vector<string> >result; vector<string>matrix(n, string(n, '.')); dfs(result, matrix, 1, n); return result; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。