7-1 图的先深搜索
朴素的 DFS
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
| #include<bitsdc++.h>
using namespace std;
int head[11];
bool vis[11];
int n,m,a,cnt,t;
struct edge{
int to;
int last;
}e[51];
void add(int x,int y){
cnt++;
e[cnt].to=y;
e[cnt].last=head[x];
head[x]=cnt;
}
void dfs(int k){
if(t==n) return;
vis[k]=true;
t++;
cout<<k<<" ";
for(int i=head[k];i>=1;i=e[i].last){
if(!vis[e[i].to]) dfs(e[i].to);
}
}
int main(){
cin>>n>>m>>a;
while(m--){
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
}
dfs(a);
if(t<n)
cout<<endl<<0;
return 0;
}
|
7-2 有序部分排列
组合数排列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <bitsdc++.h>
using namespace std;
int n,m;
int a[11];
int t=0;
void zuc(int s){
if(t==m){
for(int i=1;i<=t;i++)
cout<<a[i]<<" ";
cout<<endl;
return;
}
for(int i=s;i<=n-m+t+1;i++){
a[++t]=i;
zuc(i+1);
t--;
}
}
int main(){
cin>>n>>m;
zuc(1);
return 0;
}
|
7-3 DFS
DFS
中心在一条直线上的三个字母，即枚举三个点检查是否符合要求
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include <iostream>
#include <cstdio>
#include <cstring>
#define N 110
using namespace std;
char mp[N][N];
int v[30][30][30];
int gcd(int x, int y) {
if(y > x) swap(x, y);
if(!y) return x;
return gcd(y, x % y);
}
int ans = 0;
int n;
void dfs(int x, int y) {
for(int i = x; i <= n; ++i) {
for(int j = y; j <= n; ++j) {
if(mp[i][j] <= 'Z' && mp[i][j] >= 'A' && (x != i || y != j)) {
int dx = i - x, dy = j - y;
int dt = gcd(dx, dy);
dx /= dt, dy /= dt;
for(int nx = i + dx, ny = j + dy; nx <= n && ny <= n; nx += dx, ny += dy) {
if(mp[nx][ny] <= 'Z' && mp[nx][ny] >= 'A' && !v[mp[x][y]-'A'][mp[i][j]-'A'][mp[nx][ny]-'A']) {
ans ++;
v[mp[x][y]-'A'][mp[i][j]-'A'][mp[nx][ny]-'A'] = 1;
}
}
}
}
}
}
void dfs2(int x, int y) {
for(int i = x + 1; i <= n; ++i) {
for(int j = y - 1; j; --j) {
if(mp[i][j] <= 'Z' && mp[i][j] >= 'A') {
int dx = i - x, dy = y - j;
int dt = gcd(dx, dy);
dx /= dt, dy /= dt;
for(int nx = i + dx, ny = j - dy; nx <= n && ny >= 1; nx += dx, ny -= dy) {
if(mp[nx][ny] <= 'Z' && mp[nx][ny] >= 'A' && !v[mp[x][y]-'A'][mp[i][j]-'A'][mp[nx][ny]-'A']) {
ans ++;
v[mp[x][y]-'A'][mp[i][j]-'A'][mp[nx][ny]-'A'] = 1;
}
}
}
}
}
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%s", mp[i]+1);
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
if(mp[i][j] <= 'Z' && mp[i][j] >= 'A') {
dfs(i, j);
dfs2(i, j);
}
}
}
printf("%d", ans);
return 0;
}
|
7-4 N 皇后问题
经典搜索题，dfs 行数，枚举每列位置
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
| #include<bitsdc++.h>
using namespace std;
int n,cnt,q[11];
bool able(int r){
for(int i=0;i<r;i++){
if(q[i]==q[r]||r-i==abs(q[r]-q[i])){
return 0;
}
}
return 1;
}
void dfs(int r){
if(r==n){
cnt++;
return;
}
for(int i=0;i<n;i++){
q[r]=i;
if(able(r)){
dfs(r+1);
}
}
}
int main(){
cin>>n;
if(n>3) dfs(0);
if(n==1) cnt=1;
cout<<cnt;
return 0;
}
|
7-5 走迷宫
4 个方向，依次遍历，搜索
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
| #include<bitsdc++.h>
using namespace std;
int m,n,sx,sy,ex,ey;
char ma[101][101];
int a[101][101];
int flag=0;
void dfs(int x,int y){
int nxt[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
if(x==ex&&y==ey&&flag==0){
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(j!=n-1){
cout<<ma[i][j]<<" ";
}
else{
cout<<ma[i][j]<<endl;
}
}
}
flag=1;
return;
}
int tx=x,ty=y;
for (int i=0;i<4;i++){
tx=x+nxt[i][0];
ty=y+nxt[i][1];
if(tx<0||ty<0||tx>=m||ty>=n)
continue;
if (a[tx][ty]==0&&ma[tx][ty]=='.'){
a[tx][ty]=1;
ma[tx][ty]='*';
dfs(tx, ty);
ma[tx][ty]='o';
a[tx][ty]=0;
}
}
}
int main(){
cin>>m>>n;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
cin>>ma[i][j];
}
}
cin>>sx>>sy>>ex>>ey;
dfs(sx,sy-1);
if(flag==0){
cout<<"None"<<endl;
}
return 0;
}
|
c7-6 子集和问题
简单搜索，每个数仅取或不取两情况，特判无解应在搜索前
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
| #include <iostream>
#include <cstdio>
#define N 10010
using namespace std;
int n,c,a[N],sum;
int v[N], tot;
void backtrack(int s){
if(sum>c || s > n + 1) return;
if(sum==c){
for(int i=1;i<=tot;i++)
cout<<v[i]<<" ";
exit(0);
}
sum+=a[s];
v[++tot] = a[s];
backtrack(s+1);
sum-=a[s];
v[tot--] = 0;
backtrack(s+1);
}
int main(){
cin>>n>>c;
for(int i=1;i<=n;i++) cin>>a[i];
int ad = 0;
for(int i = 1; i <= n; ++i) ad += a[i];
if(ad < c) cout<<"No Solution!"<<endl;
else backtrack(1);
return 0;
}
|
7-7 自然数拆分问题
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
| #include<bitsdc++.h>
using namespace std;
int a[54],t;
int n,sum;
void dfs(int s){
if(sum==n){
cout<<n<<"=";
for(int i=1;i<t;i++){
cout<<a[i]<<"+";
}
cout<<a[t];
cout<<endl;
return;
}
for(int i=s;i<=n-sum;i++){
sum+=i;
t++;
a[t]=i;
dfs(i);
sum-=i;
t--;
}
}
int main(){
cin>>n;
dfs(1);
return 0;
}
|
7-8 跳马问题
规定形式图上搜索，预先处理差值坐标即可
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
| #include <iostream>
#define N 110
using namespace std;
int m,n,k,ans,cnt;
int mp[N][N],ret[N][N];
int dx[8]={2,1,-1,-2,-2,-1,1,2};
int dy[8]={1,2,2,1,-1,-2,-2,-1};
void backtrack(int sx,int sy){
if(cnt==m*n){
ans++;
if(ans<k)
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
ret[i][j]=mp[i][j];
if(ans==k){
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++){
cout<<mp[i][j];
if(j<n) cout<<" ";
else cout<<endl;
}
exit(0);
}
return;
}
for(int i=0;i<8;i++){
int x=sx+dx[i],y=sy+dy[i];
if(x<1||x>m||y<1||y>n) continue;
if(mp[x][y]) continue;
mp[x][y]=++cnt;
backtrack(x,y);
mp[x][y]=0;
cnt--;
}
}
int main(){
cin>>m>>n>>k;
mp[1][2]=++cnt;
backtrack(1,2);
if(!ans) cout<<"impossible"<<endl;
else{
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cout<<ret[i][j];
if(j<n) cout<<" ";
else cout<<endl;
}
}
}
return 0;
}
|
7-9 小猫爬山
经典搜索题，小剪枝，需要排序能够更快得到结果
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
| #include <iostream>
#include <algorithm>
#define N 20
using namespace std;
int n,w,c[N],sum[N],ret=N;
void backtrack(int u,int k){
if(k>=ret) return;
if(u==n){
ret=k;
return;
}
for(int i=0;i<k;i++){
if(sum[i]+c[u]<=w){
sum[i]+=c[u];
backtrack(u+1,k);
sum[i]-=c[u];
}
}
sum[k]=c[u];
backtrack(u+1,k+1);
sum[k]-=c[u];
}
int main(){
cin>>n>>w;
for(int i=0;i<n;i++) cin>>c[i];
sort(c,c+n,greater<int>{});
backtrack(0,0);
cout<<ret;
return 0;
}
|
7-10 种苹果
贪心+剪枝
排序权重大的水壶，在搜索时尽量向v靠拢即可，不用搜索全部情况
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
| #include <iostream>
#include <algorithm>
#define N 1010
typedef long long LL;
using namespace std;
LL v,g,w,gsum,wsum,gret,wret, sum[5];
struct bottle{
LL cnt,grow,water;
bool operator < (const bottle &a) const{
return (double)grow/water>(double)a.grow/a.water;
}
}b[6];
void backtrack(int x){
if(gsum>=v){
if(wret==wsum) gret=min(gret,gsum);
else gret=gsum;
wret=wsum;
return;
}
if(x > 4) return;
LL j = b[x].cnt, i = 1;
while(j * b[x].grow + gsum >= v) --j;
for(i = 1, j = min(j+1, b[x].cnt); j >= 0 && i <= 10; --j, ++i) {
gsum+=b[x].grow * j; wsum+=b[x].water * j;
if(wsum <= wret && gsum + sum[x+1] >= v) backtrack(x+1);
gsum-=b[x].grow * j; wsum-=b[x].water * j;
}
}
int main(){
int t; cin>>t;
while(t--){
cin>>v;
for(int i=0;i<5;i++)
cin>>b[i].cnt>>b[i].grow>>b[i].water;
sort(b,b+5);
for(int i = 4;i >= 0; i--) {
sum[i] = b[i].cnt * b[i].grow;
sum[i] += sum[i+1];
}
gret=0; wret=1e18;
backtrack(0);
if(gret) cout<<wret<<" "<<gret<<endl;
else cout<<"Impossible!"<<endl;
}
return 0;
}
|
