深搜题库
排列问题：
排列问题
基本思路+代码：
#include <bits/stdc++.h>
using namespace std;
int n,r,a[11];
int ji[11];
void f(int x)
{
if(x==r)//到达排列上线
{
for(int i=1;i<=r;i++)//输出排列
{
cout<<a[i]<<' ';
}
cout<<'\n';
return;
}
for(int i=1;i<=n;i++)
{
if(ji[i]==0)//i数没用过才能执行
{
ji[i]=1;//表示i数已经用过
a[x+1]=i;//记录i
f(x+1);//进入下一层
ji[i]=0;//return后恢复
}
}
}
int main(){
cin>>n>>r;
f(0);
return 0;
}组合问题：
组合问题
基本思路+代码：
#include <bits/stdc++.h>
using namespace std;
int n,r,a[11];
void f(int x,int st)//为从小到大排序，加上一个st，st=最近加入的数+1
{
if(x==r)
{
for(int i=1;i<=r;i++)
{
cout<<a[i]<<' ';
}
cout<<'\n';
return;
}
for(int i=st;i<=n;i++)//从st开始，保证从小到大
{
a[x+1]=i;//不需要数组记录，因为st可以保证不重复
f(x+1,i+1);
}
}
int main(){
cin>>n>>r;
f(0,1);
return 0;
}进阶：素数圈
基本思路：
在加入a数组时就判断与前一个相加是否为素数， 在最后再判断a数组中第一个与最后一个相加是否为素数。
#include <bits/stdc++.h>
using namespace std;
int n,a[22],b[22];
int ji[22];
int pz(int x)//判断素数 是返回1，否返回2
{
if(x<2) return 0;
for(int i=2;i<=x/i;i++)
{
if(x%i==0) return 0;
}
return 1;
}
void f(int x)
{
if(x==n)
{
if(!pz(a[1]+a[n]))//判断a数组中第一个与最后一个相加是否为素数
{
return;
}
for(int i=1;i<=n;i++)
{
cout<<a[i]<<' ';
}
cout<<'\n';
return;
}
for(int i=2;i<=n;i++)//1不用再考虑
{
if(ji[i]==0&&pz(a[x]+i))//判断与前一个相加是否为素数
{
ji[i]=1;
a[x+1]=i;
f(x+1);
ji[i]=0;
}
}
}
int main(){
cin>>n;
ji[1]=1;//第一个数始终为"1"
a[1]=1;
f(1);
return 0;
}迷宫问题
与宽搜的区别：
宽搜：最短路长多少/ 深搜：有多少条路径
【入门】迷宫路线问题
基本思路+代码：
#include <bits/stdc++.h>
using namespace std;
int n,s[11][11],cnt,ji[11][11];
int dx[]={-1,0,1,0,-1,1,-1,1},dy[]={0,-1,0,1,-1,1,1,-1};
void f(int px,int py)
{
if(px==1&&py==n)//到达终点
{
cnt++;
return;
}
for(int i=0;i<8;i++)//向8个方向走
{
int nx=px+dx[i],ny=py+dy[i];
if(nx<=n&&nx>0&&ny<=n&&ny>0&&s[nx][ny]==0&&ji[nx][ny]==0)//没出边界&&能走&&没走过（此条路径）
{
ji[nx][ny]=1;//记录走过了
f(nx,ny);
ji[nx][ny]=0;//还原
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)//输入
{
for(int j=1;j<=n;j++)
{
cin>>s[i][j];
}
}
ji[1][1]=1;//起点不能再走
f(1,1);
cout<<cnt;
}N皇后
基本思路+代码：
#include <bits/stdc++.h>
using namespace std;
int n,cnt;
int row[15],col[15],v1[30],v2[30];
void f(int l){
if(l==n)
{
cnt++;
if(cnt>3) return;
for(int i=0;i<l;i++)
{
cout<<row[i]<<' ';//输出每行的皇后位置
}
cout<<'\n';
return;
}
for(int i=1;i<=n;i++)
{
if(!col[i]&&!v1[i+l]&&!v2[i-l+n])
{
row[l]=i;//行记录
col[i]=1;//列记录
v1[i+l]=1;//对角线1记录
v2[i-l+n]=1;//对角线2记录
f(l+1);
col[i]=0;//列还原
v1[i+l]=0;//对角线1还原
v2[i-l+n]=0;//对角线2还原
}
}
}
int main(){
cin>>n;
f(0);
cout<<cnt;
return 0;
}取数游戏
基本思路+代码：
#include <bits/stdc++.h>
using namespace std;
const int N=10;
int T,n,m,a[N][N],s[N][N],mx=-1e9;
void f(int x,int y,int sum)
{
mx=max(mx,sum);//每次判断一下
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if((i>x||i==x&&j>y)&&s[i][j]==0)//该位置在上一个位置后面&&能走
{
for(int k=i-1;k<=i+1;k++)
for(int l=j-1;l<=j+1;l++)
s[k][l]++;//记录不能再取的位置
f(i,j,sum+a[i][j]);
for(int k=i-1;k<=i+1;k++)
for(int l=j-1;l<=j+1;l++)
s[k][l]--;//坑！不是s[k][l]=0
}
}
}
}
int main(){
cin>>T;
while(T--)
{
mx=-1e9;//初始化
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
f(0,0,0);
cout<<mx<<'\n';
}
return 0;
}