首先通过上台阶这道题 我们理解了搜索树这个东西
1.就像树结构一样 向深处搜索 每一个路径一定会走到头 走到头以后回溯 继续往可以走的路径移动..再回溯 回溯个人理解：n个子节点的状态都需由父节点推出 所以父节点每次推子节点的时候初始状态是相同的 需要子节点恢复到之前的状态得到父节点 这便是回溯
2.使用栈
3.空间O(n)
4.不具有最短性
重点 回溯与剪枝
[acwing92递归实现指数型枚举] [c++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include<bits/stdc++.h>
using namespace std;
const int N=1000;
int n;
int st[N],p[N];//1表示选 2表示不选
void dfs(int x)
{
if(x>n) //枚举到第n+1个位置 那么说明前面n个排完了 输出
{
for(int i=1;i<=n;i++)
{
if(st[i]==1) cout<<i<<" ";
}
cout<<endl;
return;
}
st[x]=1;//如果选
dfs(x+1);//这个位置选了之后 进行标记 看下个位置
st[x]=0;//回溯 恢复现场
st[x]=2;//不选
dfs(x+1);
st[x]=0;
}
int main()
{
cin>>n;
dfs(1);
return 0;
}
|
对于字典序不重复排列 那么我们还是以 依次枚举每个位置枚举应该放哪个数的思路
之前那道对于一个数由三个状态 选 不选 没考虑到
而这道题因为要以字典序排列 所以只有 用了和没用两个状态
[洛谷] [c++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include<bits/stdc++.h>
using namespace std;
const int N=1000;
int n;
bool st[N];
int p[N];
void dfs(int x) //熟悉的味道 还是枚举位置
{
if(x>n)
{
for(int i=1;i<=n;i++) cout<<p[i]<<" ";
cout<<endl;
return; //注意这有一步输出后回到其父节点的状态
}
for(int i=1;i<=n;i++)
{
if(!st[i]) //如果这个数没用过
{
p[x]=i; // 这个位置就填它
st[i]=true; //用过了
dfs(x+1);
p[x]=0; //恢复现场
st[i]=false;
}
}
}
int main()
{
cin>>n;
dfs(1);
return 0;
}
|
n个元素抽r个组合 这个就有所不同了
如 5 3
就有123 124 125 134 135
因为是组合 不难发现前位数一定是大于后位数的
[输出数字组合] [c++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include<bits/stdc++.h>
using namespace std;
const int N=1000;
int n,r;
int arr[N];//记录选了哪些数
void dfs(int x,int start )//start记录当前位置从几开始枚举
{
if(x>r)
{
for(int i=1;i<=r;i++) cout<<setw(3)<<arr[i];
cout<<endl;
return;
}
for(int i=start;i<=n;i++)
{
arr[x]=i;
dfs(x+1,i+1);
arr[x]=0;
}
return 0;
}
int main()
{
cin>>n>>r;
dfs(1,1);
return 0;
}
|
[P1036选数] [c++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| include<bits/stdc++.h>
using namespace std;
const int N = 100;
int q[N],arr[N];
int n,k;
int cnt=0;
bool is_prime(int sum)
{
if(sum<2) return false;
for(int i=2;i<=sqrt(sum);i++)
{
if(sum%i==0) return false;
}
return true;
}
void dfs(int x,int start)
{
if(x>k)
{
int sum=0;
for(int i=1;i<=k;i++)
{
sum+=arr[i];
}
if(is_prime(sum)) cnt++;
return;
}
for(int i=start;i<=n;i++)
{
arr[x]=q[i];
dfs(x+1,i+1);
arr[x]=0;
}
return;
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>q[i];
dfs(1,1);
cout<<cnt<<endl;
return 0;
}
|
首先得注意 输入的是字符 所以不能直接cin>>a[i][j] (没有输出 我想了二十分钟为什么)
其次 其实遇到一个没有used的 就cnt++ 再从这个点搜一下就行了很简单
[P1451细胞数量] [c++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include<bits/stdc++.h>
using namespace std;
int n,m,cnt=0;
int a[120][120];
bool used[120][120];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void dfs(int x,int y)
{
used[x][y]=1;
for(int i=0;i<4;i++)
{
int nx=x+dx[i];
int ny=y+dy[i];
if(used[nx][ny]==1 || a[nx][ny]==0) continue;
dfs(nx,ny);
}
}
int main()
{
cin>>n>>m;
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
char c;
cin>>c;
a[i][j]=c-'0';
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]!=0 &&used[i][j]==0)
{
dfs(i,j);
cnt++;
}
}
}
cout<<cnt;
return 0;
}
|
