题目条件n−皇后问题是指将n个皇后放在n×n的国际象棋棋盘上使得皇后不能相互攻击到即任意两个皇后都不能处于同一行、同一列或同一斜线上。现在给定整数n请你输出所有的满足条件的棋子摆法。输入格式共一行包含整数n。输出格式每个解决方案占n行每行输出一个长度为n的字符串用来表示完整的棋盘状态。其中.表示某一个位置的方格状态为空Q表示某一个位置的方格上摆着皇后。每个方案输出完成后输出一个空行。注意行末不能有多余空格。输出方案的顺序任意只要不重复且没有遗漏即可。数据范围1≤n≤9有两种解法第一种是按行搜索第二种是对每一个格子都进行“放与不放”的考虑第一种解法//按行搜索 #include bits/stdc.h using namespace std; const int N10; int n; char g[N][N]; bool col[N],dg[N],udg[N];//分别代表列正对角线反对角线 void dfs(int r) { if(rn) { for(int i0;in;i) { puts(g[i]); } puts( ); return; } for(int i0;in;i) { if(!col[i]!dg[ir]!udg[i-rn])//正对角线的函数可写作y-xb反对角线的函数可写作yxb通过y与x的运算并设置偏移量n可以使得同一条对角线上的下标相同 { g[r][i]Q; col[i]dg[ir]udg[i-rn]true; dfs(r1); g[r][i].;//恢复现场 col[i]dg[ir]udg[i-rn]false; } } } int main() { cinn; for(int i0;in;i) { for(int j0;jn;j) { g[i][j].; } } dfs(0); return 0; }第二种解法//另一种搜索顺序对每一个格子都进行“放与不放”的考虑 #include bits/stdc.h using namespace std; const int N10; int n; bool row[N],col[N],dg[N],udg[N]; char g[N][N]; void dfs(int r,int c,int s)//分别代表行列和目前已放置的皇后数量 { if(cn) c0,r;//这一行结束了换到下一行 if(rn)//枚举完最后一行了 { if(sn)//找到一组解 { for(int i0;in;i) puts(g[i]); puts( ); } return; } //不放皇后 dfs(r,c1,s); //放皇后 if(!row[r]!col[c]!dg[rc]!udg[r-cn]) { g[r][c]Q; row[r]col[c]dg[rc]udg[r-cn]true; dfs(r,c1,s1); g[r][c].; row[r]col[c]dg[rc]udg[r-cn]false; } } int main() { cinn; for(int i0;in;i) { for(int j0;jn;j) { g[i][j].; } } dfs(0,0,0);//从左上角开始 return 0; }