排列数字
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;
const int N=1e5+5;
typedef pair<int,int> PII;
int n;
bool st[N];
int path[N];
void dfs(int pos)
{
//设置边界
if(pos==n+1)
{
for(int i=1;i<=n;i++) printf("%d ",path[i]);
cout<<endl;
return;
}
//从i到n之间选数
for(int i=1;i<=n;i++)
{
if(!st[i])
{
//设置状态
path[pos]=i;
st[i]=true;
//dfs下去
dfs(pos+1);
//恢复现场
path[pos]=0;
st[i]=false;
}
}
}
int main()
{
cin>>n;
dfs(1);//0号位置开始
return 0;
}
蓝桥杯 方格分割
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const int N=1e6+5;
typedef long long LL;
typedef pair<int,int> PII;
int dir[][2]= {{1,0},{-1,0},{0,1},{0,-1}};
bool st[7][7];
int cnt;
void dfs(int x,int y)
{
//走到边界说明是一种方案,cnt++
if(x==0||y==0||x==6||y==6)
{
cnt++;
return ;
}
//dfs主体,向四个方向深入
for(int i=0; i<4; i++)
{
int nx=x+dir[i][0];
int ny=y+dir[i][1];
//走出地图或者走过了,不符合continue下一个
if(nx<0||nx>6||ny<0||ny>6||st[nx][ny]==true) continue;
//如果这点没有走过dfs该点
if(!st[nx][ny])
{
//对当前对进行标记,最后要恢复现场,回溯
st[nx][ny]=true;
//对对称点也进行标记(本题要求)
st[6-nx][6-ny]=true;
//dfs下去
dfs(nx,ny);
//回溯,恢复现场,开始时怎么样,结束时也要怎么样
st[nx][ny]=false;
st[6-nx][6-ny]=false;
}
}
}
int main()
{
st[3][3]=true;
//从中心开始向四周
dfs(3,3);
cout<<0.25*cnt<<endl;
}
n-皇后问题
#include <iostream>
using namespace std;
const int N = 20;
// bool数组用来判断搜索的下一个位置是否可行
// col列,dg对角线,udg反对角线
// g[N][N]用来存路径
int n;
char g[N][N];
bool col[N], dg[N], udg[N];
void dfs(int u) {
// u == n 表示已经搜了n行,故输出这条路径
if (u == n) {
for (int i = 0; i < n; i ++ ) puts(g[i]); // 等价于cout << g[i] << endl;
puts(""); // 换行
return;
}
//对n个位置按行搜索
for (int i = 0; i < n; i ++ )
// 剪枝(对于不满足要求的点,不再继续往下搜索)
// udg[n - u + i],+n是为了保证下标非负
if (!col[i] && !dg[u + i] && !udg[n - u + i]) {
g[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; // 恢复现场 这步很关键
g[u][i] = '.';
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
g[i][j] = '.';
dfs(0);
return 0;
}