经典的N皇后问题,可以通过回溯的方式进行求解,我这里使用递归实现 II只是统计了I的解的规模
bool iscan(int x,int y,vector<string>map){ for(int i=0;i<x;i++) for(int j=0;j<map[0].size();j++) if(map[i][j]=='Q'){ if(j==y||i+j==x+y||i-j==x-y)return false; } return true; } void NQueens(int N,vector<vector<string> >&res,vector<string>t,int k){ if(N==k){res.push_back(t);return;} for(int i=0;i<N;i++) if(iscan(k,i,t)){ t[k][i]='Q'; NQueens(N,res,t,k+1); t[k][i]='.'; } } class Solution { public: vector<vector<string> > solveNQueens(int n) { vector<vector<string> > res; vector<string>t; if(n==1){t.push_back("Q");res.push_back(t);return res;} if(n<=3)return res; string s=""; for(int i=0;i<n;i++) s+='.'; for(int i=0;i<n;i++){ t.push_back(s); } NQueens(n,res,t,0); return res; } };
N-Queens II
bool iscan(int x,int y,vector<string>map){ for(int i=0;i<x;i++) for(int j=0;j<map[0].size();j++) if(map[i][j]=='Q'){ if(j==y||i+j==x+y||i-j==x-y)return false; } return true; } void NQueens(int N,int &res,vector<string>t,int k){ if(N==k){res++;return;} for(int i=0;i<N;i++) if(iscan(k,i,t)){ t[k][i]='Q'; NQueens(N,res,t,k+1); t[k][i]='.'; } } class Solution { public: int totalNQueens(int n) { int res=0; vector<string>t; if(n==1)return 1; if(n<=3)return res; string s=""; for(int i=0;i<n;i++) s+='.'; for(int i=0;i<n;i++){ t.push_back(s); } NQueens(n,res,t,0); return res; } };