zhi识点
1.只要是能画出树形结构的,就可以用搜索来写
写法1:全排列
#include<bits/stdc++.h>
using namespace std;
int n;
int col[10], dg[20], udg[20];//注意ug和udg要开到两倍
char g[10][10];
void dfs(int x)//枚举的是行,即x
{
if(x == n)
{
for(int i = 0; i < n; ++ i)
cout << g[i] << endl;
cout << endl;
}
for(int i = 0; i < n; ++ i)//枚举的是列,即y
{
if(!col[i] && !dg[x + i] && !udg[n - x + i])//截距
{
g[x][i] = 'Q';
col[i] = dg[x + i] = udg[n - x + i] = 1;
dfs(x + 1);
col[i] = dg[x + i] = udg[n - x + i] = 0;
g[x][i] = '.';
}
}
}
int main()
{
cin >> n;
for(int i = 0; i < n; ++ i)
for(int j = 0; j < n; ++ j)
g[i][j] = '.';
dfs(0);
}
写法2:每次选和不选
#include<bits/stdc++.h>
using namespace std;
int n;
bool row[10], col[10], dg[20], udg[20];//dg和udg要开两倍
char g[10][10];
void dfs(int x, int y, int s)
{
if(y == n) y = 0, x ++;
if(x == n)
{
if(s == n)
{
for(int i = 0; i < n; ++ i)
cout << g[i] << endl;
cout << endl;
}
return;
}
//不选
dfs(x, y + 1, s);
//选
if(!row[x] && !col[y] && !dg[x + y] && !udg[n - x + y])//截距
{
g[x][y] = 'Q';
row[x] = col[y] = dg[x + y] = udg[n - x + y] = 1;
dfs(x, y + 1, s + 1);
row[x] = col[y] = dg[x + y] = udg[n - x + y] = 0;
g[x][y] = '.';
}
}
int main()
{
cin >> n;
for(int i = 0; i < n; ++ i)
for(int j = 0; j < n; ++ j)
g[i][j] = '.';
dfs(0, 0, 0);
}
?
?