题目
n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
示例 1：
输入：n = 4 输出：2 解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1 输出：1
解题
方法一：回溯
class Solution { public: int res=0; void dfs(vector<string>& chessboard,int n,int row){ if(row==n){ res++; return; } for(int col=0;col<n;col++){ if(isValid(chessboard,n,row,col)){ chessboard[row][col]='Q'; dfs(chessboard,n,row+1); chessboard[row][col]='.'; } } } bool isValid(vector<string>& chessboard,int n,int row,int col){ for(int i=0;i<row;i++){ if(chessboard[i][col]=='Q') return false; } for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){ if(chessboard[i][j]=='Q') return false; } for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){ if(chessboard[i][j]=='Q') return false; } return true; } int totalNQueens(int n) { vector<string> chessboard(n,string(n,'.')); dfs(chessboard,n,0); return res; } };
