搜索专题

字数统计: 3.7k字   |   阅读时长: 19min

搜索专题

一.DFS

1.递归

小练手

**
输出1到n的所有排列，要求按照字典序从到
输出。**

输入

3

输出

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

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<bits/stdc++.h>
using namespace  std;
int n,vis[10000000],b[10000000];
void qpl(int a,int tmp)
{
	for(int i=1;i<=n;i++)
	{
		if(tmp==n)
		{
			for(int j=1;j<=n;j++)
			cout<<b[j]<<" ";
			cout<<endl;
			return;
		}
		if(!vis[i])
		{
			vis[i]=1;
			b[a]=i;
			qpl(a+1,tmp+1);
			vis[i]=0;
		}
	}
	return;
}
int main()
{
	cin>>n;
	qpl(1,0);
	return 0; 
}

2.深度优先搜索

小练手

给定一个n行m列的迷宫，0代表障碍物，1代
表可以行走的区域。
每次可以朝着上下左右4个方向移动
起点在迷宫的左上⻆，终点在迷宫的右下⻆，问是否存在一条路径从起点到终点。

输入

3 6
100100
110111
011101
000011

输出

YES

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;
int n,m;
char a[10000][10000];
int vis[10000][10000],ans;
int tmp[5][2]={{0,0},{1,0},{-1,0},{0,1},{0,-1}};
void dfs(int x,int y)
{
	if(x==m&&y==n)
	{
		ans++;
		return;
	}
	for(int i=1;i<=4;i++)
	{
		if(x+tmp[i][0]>0&&x+tmp[i][0]<=m&&y+tmp[i][1]>0&&y+tmp[i][1]<=n)
		if(!vis[x+tmp[i][0]][y+tmp[i][1]]&&a[x+tmp[i][0]][y+tmp[i][1]]=='1')
		{
			vis[x+tmp[i][0]][y+tmp[i][1]]=1;
			dfs(x+tmp[i][0],y+tmp[i][1]);
			vis[x+tmp[i][0]][y+tmp[i][1]]=0;
		}
	}
	return;
}
int main()
{
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++)
	scanf("%s",a[i]+1);
	vis[1][1]=1;
	dfs(1,1);
	if(ans>=1) printf("YES\n");
	else printf("NO\n");
	return 0;
}

八皇后

一道经典老题。

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
#include<bits/stdc++.h>
using namespace std;
struct node
{
	int x,y;
}ans[20];
int h[20],l[20],an,n;
int vis[3][50];
void dfs(int x)
{	
	if(x==n+1)
	{
		an++;
		if(an<=3)
		{
			for(int i=1;i<=n;i++)
			{
				printf("%d ",ans[i].y);
			}
			cout<<endl;
		}
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis[1][x+i]&&!vis[2][x-i+15]&&!h[i])
		{
			vis[1][x+i]=vis[2][x-i+15]=1;
			h[i]=1;
			ans[x].x=x;
			ans[x].y=i;
			dfs(x+1);
			h[i]=0;
			vis[1][x+i]=vis[2][x-i+15]=0;
		}
	}
	return;
}
int main()
{
	cin>>n;
	dfs(1);
	printf("%d",an); 
	return 0;
}
反思：

这道题并不难，但是想要一次AC并不容易，用for循环进行判断的话只能得90分。所以要想其他判断方法，如用数组进行判断：如果(x1,y1)与(x2,y2)共线，x1-x2=y1-y2 => x1-y1=x2-y1 或 x1-x2=y2-y1 => x1+y1=x2+y2;

3.迭代加深搜索

实质还是一种DFS。迭代加深搜索本质上还是一种DFS，只不过每次给DFS的层数加上了限制。每次搜到指定的层数，即使能继续往下搜索也不再向下了，而是回溯回去。指定的层数依次增加，知道找到最优解。

小练手

跳房子是大家小时候的体育游戏之一，游戏的规则简单易懂、具有可变性。我
们在地上画出一个个房子，然后扔石子，根据石子的落地位置确定跳到哪个
房子。我们将房子抽象为x轴上的连续的正整数坐标点，第i个房子的坐标为
i，并假设房子个数无限。
我们的游戏规则如下：
1. 石子落到房子内，记为H，我们可以跳到当前坐标的3倍坐标位置。
2. 石子落到房子外，记为O，我们需跳回当前坐标折半并向下取整的坐标位
置。
例如，初始在第1个房子，要想到达第6个房子，既可以HHHOO，也可以
HHOHO。
请你编一个程序，给出从第n个房子到第m个房子所需要的最少跳跃次数k和
石子的扔法。
若最少跳跃次数下存在多种扔法，则选取字典序最小的扔法。

输入

1 6

输出

5
HHHOO 

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<bits/stdc++.h>
using namespace std;
int n,m,ans=1,a[30],an;
bool dfs(int x,int ans,int tmp)
{
	if(tmp>ans) return 0;
	a[tmp]=0;
	if(3*x==m) return 1;
	if(!dfs(3*x,ans,tmp+1))
	{
		a[tmp]=1;
		if(x/2==m) return 1; 
		dfs(x/2,ans,tmp+1);
	}
	else return 1;
}
int main()
{
	scanf("%d%d",&n,&m);
	while(!dfs(n,ans,1)&&!an)
	{
		ans++;
	}
	printf("%d\n",ans);
	for(int i=1;i<=ans;i++)
	{
		if(a[i]==0) printf("H");
		if(a[i]==1) printf("O");
	}
	return 0;
}
作业：

  1. 四子连棋

  2. **埃及分数Problem
    在古埃及，人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理 数。如：2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。
    对于一个分数a/b,表示方法有很多种，但是哪种最好呢？
    首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。
    如： **

    19/45=1/3 + 1/12 + 1/180

    **19/45=1/3 + 1/15 + 1/45 **

    19/45=1/3 + 1/18 + 1/30

    **19/45=1/4 + 1/6 + 1/180 **

    19/45=1/5 + 1/6 + 1/18.

    **最好的是最后一种，因为1/18比1/180,1/45,1/30,1/180都大。
    给出a,b(0〈a〈b〈1000),编程计算最好的表达方式。 **

    **Input

第一行:N 表示有N组测试数据，每组测试数据为一行包a,b(0〈a〈b〈1000)。**

**Output
每组测试数据若干个数，自小到大排列，依次是单位分数的分母。 **

Sample Input

1

19 45

Sample Output

5 6 18

二.BFS

1. 广度优先搜索

小练手

国际象棋中，马的走法为日字形，n*m的棋盘中有k个障碍物，马不能跳到这些上面，求从给定起点跳到终点的最短步数。

2. 双向BFS

BFS的时间复杂度随层数增加而呈指数递增，双向BFS能极大的优化时间复杂度

小练手

给定一个n行m列的迷宫，0代表障碍物，1代
表可以行走的区域。
每次可以朝着上下左右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
#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[10000][10000];
int vis1[10000][10000],vis2[10000][10000],ans;
int tmp[5][2]={{0,0},{1,0},{-1,0},{0,1},{0,-1}};
int two_way_bfs()
{
	queue<pair<int,int> > q1,q2;
	q1.push(make_pair(1,1));
	q2.push(make_pair(n,m));
	while(1)
	{
		int x=q1.front().first,y=q1.front().second;
		q1.pop();
		for(int i=1;i<=4;i++)
		{
			if(a[x+tmp[i][0]][y+tmp[i][1]]=='1'&&!vis1[x+tmp[i][0]][y+tmp[i][1]])
			{
				q1.push(make_pair(x+tmp[i][0],y+tmp[i][1]));
				vis1[x+tmp[i][0]][y+tmp[i][1]]=vis1[x][y]+1;
				if(vis2[x+tmp[i][0]][y+tmp[i][1]]) return vis1[x+tmp[i][0]][y+tmp[i][1]]+vis2[x+tmp[i][0]][y+tmp[i][1]];
			}
		}
		x=q2.front().first,y=q2.front().second;
		q2.pop();
		for(int i=1;i<=4;i++)
		{
			if(a[x+tmp[i][0]][y+tmp[i][1]]=='1'&&!vis2[x+tmp[i][0]][y+tmp[i][1]])
			{
				q2.push(make_pair(x+tmp[i][0],y+tmp[i][1]));
				vis2[x+tmp[i][0]][y+tmp[i][1]]=vis2[x][y]+1;
				if(vis1[x+tmp[i][0]][y+tmp[i][1]]) return vis1[x+tmp[i][0]][y+tmp[i][1]]+vis2[x+tmp[i][0]][y+tmp[i][1]];
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	scanf("%s",a[i]+1);
	vis1[1][1]=0;
	vis2[n][m]=0;
	ans=two_way_bfs();
	printf("%d",ans);
	return 0;
}
注意

在双向BFS中，两个方向同扩一个点等同于同时扩一层。

三.搜索的优化小技巧

  1. 搜索的顺序：从大到小或者从小到大排序之后再进行搜索，可能会达到意想不到结果。
  2. 最优化剪枝：如果当前的步骤加上后面都是最优的选择，还不能已有的答案更优就直接退出。
  3. 可行性剪枝的应用。
  4. 不同的题有不同的优化技巧，需要大家自己领会

任务

  1. 数独

  2. 如果两个相邻像素灰度的差值不超过M，这两个像素就算同个区
    域。如果像素a和像素b是1个区域，像素b和像素c是1个区域，那么a和
    c也是1个区域请注意，若两个相邻像素灰度的差值1于M，也未必不是1个区域。
    给定1个灰度图和M，问这个图像可以分割成多少个不同的

    输入

    3 4 1


2 0 0 0
0 0 2 2
0 0 2 2 

**输出**

3

四.模拟退火

模拟退火算法描述：

     若J( Y(i+1) )>= J( Y(i) )  (即移动后得到更优解)，则总是接受该移动

     若J( Y(i+1) )< J( Y(i) )  (即移动后的解比当前解要差)，则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低（逐渐降低才能趋向稳定）

任务

  1. 均分数据

搜索测试反思

1.ping

这道题与跳石头(P2678)类似，用二分答案就能AC。

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
#include<bits/stdc++.h>
using namespace std;
int a,b,s[10000000];
bool check(int mid)
{
	int tmp[100000],cnt=1;
	tmp[cnt]=s[1];
	for(int i=2;i<=a;i++)
	{
		if(s[i]-tmp[cnt]>=mid) tmp[++cnt]=s[i];
	}
	if(cnt>=b) return 1;
	else return 0;
}
int main()
{
	freopen("ping.in","r",stdin);
	freopen("ping.out","w",stdout);
	scanf("%d %d",&a,&b);
	for(int i=1;i<=a;i++)
	{
		scanf("%d",&s[i]);
	}
	int l=1,mid,r=s[a];
	while(l<r)
	{
		mid=(l+r)/2;
		if(check(mid)) l=mid+1;
		else r=mid;
	}
	int ans=r;
	printf("%d",ans-1);
	return 0;
}
教训：
以后码完代码，在提交前一定要检查freopen写对没！！！，血的教训！！

2.map

这道题并不难，因为边长为一，所以不必用spfa或Dijkstra，直接用BFS一层一层的更新顺带记录一下次数就行了。

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
#include<bits/stdc++.h>
using namespace std;
int n,m,ans[10000000];
struct node
{
	int ne,to;
}edge[10000000];
int head[10000000],cnt;
void add(int u,int v)
{
	edge[++cnt].to=v;
	edge[cnt].ne=head[u];
	head[u]=cnt;
}
int vis[10000000];
void bfs(int sta)
{
	queue<int>q;
	q.push(sta);
	vis[sta]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=edge[i].ne)
		{
			int v=edge[i].to;
			if(!vis[v]) 
			{
				q.push(v);
				ans[v]=ans[u];
				vis[v]=vis[u]+1;
			}
			else if(vis[v]>vis[u])
			{
				ans[v]+=ans[u];
			}
		}
	}
}
int main()
{
	freopen("map.in","r",stdin);
	freopen("map.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(int i=1,u,v;i<=m;i++)
	{
		scanf("%d %d",&u,&v);
		add(u,v);
		add(v,u);
	}
	ans[1]=1;
	bfs(1);
	for(int i=1;i<=n;i++)
	printf("%d\n",ans[i]);
	return 0;
}
教训：每道题两个代码，一个暴力，一个算法，对拍。

3.move

第三题才是重头戏。
有两种思路：
1.重构图，像网络流一样，分点，将点分为k+1个。

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
using namespace std;
struct node{
	int ne,to,w;
}edge[10000000];
int cnt,head[1000000];
void add(int u,int v,int w)
{
	edge[++cnt].to=v;
	edge[cnt].ne=head[u];
	edge[cnt].w=w;
	head[u]=cnt;
}
int n,m,k,s,t,ans=0x7ffffff;
int vis[1000000],dis[1000000];
void spfa(int sta)
{
	memset(dis,0x3f,sizeof(dis));//本题存在编号为0的点； 
	queue<int> q;
	q.push(sta);
	vis[sta]=1;
	dis[sta]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=edge[i].ne)
		{
			int v=edge[i].to,w=edge[i].w;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				if(!vis[v])
				{
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
}
int main()
{
	freopen("move.in","r",stdin);
	freopen("move.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	scanf("%d%d",&s,&t);
	for(int i=1,u,v,w;i<=m;i++)
	{
		scanf("%d %d %d",&u,&v,&w);
		for(int j=0;j<=k;j++)
		{
			add(u*(k+1)+j,v*(k+1)+j,w);
			add(v*(k+1)+j,u*(k+1)+j,w);
//			printf("  %d  %d\n",u*(k+1)+j,v*(k+1)+j);
			if(j!=k)
			{
				add(u*(k+1)+j,v*(k+1)+j+1,0);
				add(v*(k+1)+j,u*(k+1)+j+1,0);
//				add(v*(k+1)+j+1,u*(k+1)+j,0);
//				printf("  %d  %d\n",u*(k+1)+j,v*(k+1)+j+1);
			}
		}
	}
	spfa(s*(k+1));
	for(int i=0;i<=k;i++);
	printf("%d",dis[t*(k+1)+k]);
	return 0;
}

/*
5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100

边长为零的边是单向的；
否则会出现  0 => 5 => 7 => 4 => 6 => 9 的情况 （算出来为6，答案为8） 
*/
不过会有两个测试点TLE qwq.

2.状态转移，最短路+dis[v][i]=min(dis[u][i]+w,dis[u][i+1]);（dis[i][j]表示到i点，还有k次免费没用时的最短路径）

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
struct node
{
	int ne,to,w;
}edge[1000000];
int cnt,head[1000000],ans=0x7ffffff;
void add(int u,int v,int w)
{
	edge[++cnt].to=v;
	edge[cnt].w=w;
	edge[cnt].ne=head[u];	
	head[u]=cnt;
}
int n,m,k,s,t;
int dis[1000000][11],vis[10000000];
void spfa(int sta)
{
	memset(dis,0x3f,sizeof(dis));//本题存在编号为0的点； 
	queue<int> q;
	q.push(sta);
	vis[sta]=1;
	for(int i=0;i<=k;i++)
	dis[sta][i]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=edge[i].ne)
		{
			int v=edge[i].to,w=edge[i].w;
			for(int i=0;i<=k;i++)
			if(dis[v][i]>dis[u][i]+w||(i+1<=k&&dis[v][i]>dis[u][i+1]))
			{
				if(i+1<=k)
				dis[v][i]=min(dis[u][i]+w,dis[u][i+1]);
				else dis[v][i]=dis[u][i]+w;
				if(!vis[v])
				{
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
}
void dfs(int i,int tot)
{
	if(tot==k)
	{
		spfa(s);
		return;
	}
	for(int j=i+2;(cnt-j+1)/2>=(k-tot);j+=2)
	{
		int tmp=edge[j].w;
		edge[j].w=edge[j+1].w=0;
		dfs(j,tot+1);
		edge[j].w=edge[j+1].w=tmp;
	}
}
int main()
{
	freopen("move.in","r",stdin);
	freopen("move.out","w",stdout);
	scanf("%d %d %d",&n,&m,&k);
	scanf("%d %d",&s,&t);
	for(int i=1,u,v,w;i<=m;i++)
	{
		scanf("%d %d %d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	spfa(s);
	printf("%d",dis[t][0]);
	return 0;
}

本文作者： syrsteven
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/c4637555.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

    			  jsonContent:
				meta: false
				pages: false
				posts:
				  title: true
				  date: true
				  path: true
				  text: false
				  raw: false
				  content: false
				  slug: false
				  updated: false
				  comments: false
				  link: false
				  permalink: false
				  excerpt: false
				  categories: false
				  tags: true


There's nothing