第一种 类似于上一个题目得变形
#include<iostream> using namespace std; const int N = 20; int n; char p[N][N]; bool col[N], dg[N*2], udg[N*2];//注意范围的设置 void dfs(int u) { if (u == n) { for (int i = 0; i < n; i++) { cout << p[i] << endl;//注意这步输出 } cout << endl; return; } //求斜对角线时候用公式y=x+b来算,反对角是怕有负数,整体上移一个图形,但是位置不变 for (int i = 0; i < n; i++) { if (!col[i] && !dg[u+i] && !udg[n+u-i]) { p[u][i] = 'Q'; col[i] = dg[u + i] = udg[n + u - i] = true; dfs(u + 1); col[i] = dg[u + i] = udg[n + u - i] = false; p[u][i] = '.'; } } } int main() { cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { p[i][j] = '.'; } } dfs(0); return 0; }
第二种是一个个枚举直到成功就输出
#include<iostream> #include<algorithm> #include<vector> using namespace std; const int N = 20; int n; char p[N][N]; bool col[N],row[N], dg[N*2], udg[N*2]; void dfs(int x,int y,int s) { if(s>n) return;//皇后多了的情况,直接跳出 if(y==n){x++;y=0;}//到结尾处换行 if(x==n){ if(s==n){ for(int i=0;i<n;i++){ cout<<p[i]<<endl;} cout<<endl; } return;//注意return摆放得位置,放在for循环里就会死循环 } p[x][y]='.'; dfs(x,y+1,s);//类型于for循环中累加的操作,不停止继续,并判断 if(!col[y]&&!row[x]&&!dg[y+x]&&!udg[n+y-x]) { p[x][y]='Q'; col[y]=row[x]=dg[y+x]=udg[n+y-x]=true; dfs(x,y+1,s+1);//继续递归循环 col[y]=row[x]=dg[y+x]=udg[n+y-x]=false; p[x][y]='.'; } } int main() { cin >> n; dfs(0,0,0); return 0; }