搜索练习

搜索练习,第1张

搜索练习 一丶深度优先搜索

基本概念(Depth First Search,简称DFS):一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件,搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。

二丶广度优先搜索

宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS。是以当前的点为中心,向四处展开搜索,搜完以当前这个点为中心的所有点。他并不考虑目标点的位置,而是搜索完一张图,属于盲目的搜索。

三丶题目练习
1.题目描述

一个如下的 6 times 66×6 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

上面的布局可以用序列 2 4 6 1 3 52 4 6 1 3 5 来描述,第 ii 个数字表示在第 ii 行的相应位置有一个棋子,如下:

行号 1 2 3 4 5 61 2 3 4 5 6

列号 2 4 6 1 3 52 4 6 1 3 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出,解按字典顺序排列。
请输出前 33 个解。最后一行是解的总个数。

输入格式

一行一个正整数 nn,表示棋盘是 n times nn×n 大小的。

输出格式

前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。

输入输出样例

输入 #1复制

6

输出 #1复制

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

#include 

using namespace std;

const int N = 20;

int ans=0;
int n;
char path[N][N]; 
int a[N]; //保存棋子摆放的位置
bool col[N],dg[N],undg[N]; //分别表示行和两条对角线

void dfs(int s)
{
	if( s == n+1)
	{  
	   if(ans <=2)  
		{
		for(int i = 1 ; i <= n; i++)
		   cout << a[i] << " ";
			 cout <> n;
	dfs(1);	
	cout << ans< 
 2.题目背景 
 

kkksc03 的大学生活非常的颓废,平时根本不学习。但是,临近期末考试,他必须要开始抱佛脚,以求不挂科。

题目描述

这次期末考试,kkksc03 需要考 44 科。因此要开始刷习题集,每科都有一个习题集,分别有 s_1,s_2,s_3,s_4s1​,s2​,s3​,s4​ 道题目,完成每道题目需要一些时间,可能不等(A_1,A_2,ldots,A_{s_1}A1​,A2​,…,As1​​,B_1,B_2,ldots,B_{s_2}B1​,B2​,…,Bs2​​,C_1,C_2,ldots,C_{s_3}C1​,C2​,…,Cs3​​,D_1,D_2,ldots,D_{s_4}D1​,D2​,…,Ds4​​)。

kkksc03 有一个能力,他的左右两个大脑可以同时计算 22 道不同的题目,但是仅限于同一科。因此,kkksc03 必须一科一科的复习。

由于 kkksc03 还急着去处理洛谷的 bug,因此他希望尽快把事情做完,所以他希望知道能够完成复习的最短时间。

输入格式

本题包含 55 行数据:第 11 行,为四个正整数 s_1,s_2,s_3,s_4s1​,s2​,s3​,s4​。

第 22 行,为 A_1,A_2,ldots,A_{s_1}A1​,A2​,…,As1​​ 共 s_1s1​ 个数,表示第一科习题集每道题目所消耗的时间。

第 33 行,为 B_1,B_2,ldots,B_{s_2}B1​,B2​,…,Bs2​​ 共 s_2s2​ 个数。

第 44 行,为 C_1,C_2,ldots,C_{s_3}C1​,C2​,…,Cs3​​ 共 s_3s3​ 个数。

第 55 行,为 D_1,D_2,ldots,D_{s_4}D1​,D2​,…,Ds4​​ 共 s_4s4​ 个数,意思均同上。

输出格式

输出一行,为复习完毕最短时间。

输入输出样例

输入 #1复制

1 2 1 3		
5
4 3
6
2 4 3

输出 #1复制

20
#include 
#include 

using namespace std;

const int N = 30;
const int inf = 0x3f3f3f3f;   //表示正无穷 
int s[4];
int s_time[4][N];
int min_time; 
int l; // 左脑袋 
int r; // 右脑袋 

void dfs(int x,int y)
{
	
	if(y == s[x])
	{
		min_time = min(min_time,max(l,r)); 
		return; 
	}
	if(y > s[x])
	 return;
	// 左脑开始 
	l += s_time[x][y];
	dfs(x,y+1);
	l -= s_time[x][y];
	//右脑开始
	r += s_time[x][y];
	dfs(x,y+1);
	r = r - s_time[x][y]; 
}
int main()
{
	for(int i = 0; i < 4; i++)
	cin >> s[i];
	for(int i = 0; i < 4; i++)
	 for(int j = 0; j < s[i]; j++)
	   cin >> s_time[i][j];
	   int ans = 0; /// 保存最后的时间 
	    for(int i = 0; i < 4; i++)
		{
			l = r = 0;
			min_time = inf;  //要最小的,就先直接弄个正无穷 
			dfs(i,0); // 开搜,从第i门课的第一个题开始搜索
			ans += min_time; 
		 } 
		 cout << ans;
	return 0;
}
3.题目描述

有一个 n times mn×m 的棋盘,在某个点 (x, y)(x,y) 上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数,分别为 n, m, x, yn,m,x,y。

输出格式

一个 n times mn×m 的矩阵,代表马到达某个点最少要走几步(左对齐,宽 55 格,不能到达则输出 -1−1)。

输入输出样例

输入 #1复制

3 3 1 1

输出 #1复制

0    3    2    
3    -1   1    
2    1    4    
#include 
#include   //队列头文件
#include 

using namespace std;

typedef pair PII;

queue a;
bool b[410][410];
int res[410][410] = {0};

int main()
{
	memset(res,-1,sizeof(res));
	int ne[8][2] = {{1,-2},{2,-1},{1,2},{2,1},{-1,2},{-2,1},{-1,-2},{-2,-1}}; //八个方向
	int m, n, x, y;
	cin >> m >> n >> x >> y;
	b[x][y] = true;
	res[x][y] = 0;
	a.push({ x,y });
	bool flag = true;
	while (!a.empty())
	{
		PII term;
		term = a.front();
		a.pop();
		for (int i = 0; i < 8; i++)
		{
			int nx, ny;
			nx = term.first + ne[i][0];
			ny = term.second + ne[i][1];
			if (nx < 1 || ny < 1 || nx > m || ny > n)  continue;
			if (!b[nx][ny])
			{
				b[nx][ny] = true;
				res[nx][ny] = res[term.first][term.second] + 1; //当前这个点的步数是以头结点的步数+1
				a.push({ nx,ny }); // 入队
			}
		}
	}
	for (int i = 1; i <= m; i++)
		{
		  for (int j = 1; j <= n; j++)
			printf("%-5d", res[i][j]);
			cout << endl;
		}
	return 0;
}
4.题目描述

呵呵,有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第ii层楼(1 le i le N)(1≤i≤N)上有一个数字K_i(0 le K_i le N)Ki​(0≤Ki​≤N)。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如:3, 3 ,1 ,2 ,53,3,1,2,5代表了K_i(K_1=3,K_2=3,…)Ki​(K1​=3,K2​=3,…),从11楼开始。在11楼,按“上”可以到44楼,按“下”是不起作用的,因为没有-2−2楼。那么,从AA楼到BB楼至少要按几次按钮呢?

输入格式

共二行。

第一行为33个用空格隔开的正整数,表示N,A,B(1≤N≤200, 1≤A,B≤N)N,A,B(1≤N≤200,1≤A,B≤N)。

第二行为NN个用空格隔开的非负整数,表示K_iKi​。

输出格式

一行,即最少按键次数,若无法到达,则输出-1−1。

输入输出样例

输入 #1复制

5 1 5
3 3 1 2 5

输出 #1复制

3
	#include 
	#include 
	
	using namespace std;
	
	const int N = 210;
	
	int inf = 0x3f3f3f3f;
	int book[N];
	int path[N];
	int a,b,n;
	int res = inf;
	
	void dfs(int x,int s)
	{
		
		if(x == b)  {
		 res = min(res,s);
		 return;
	    }                                        
	    if(s >= res)
	      return;
		  book[x] = true;
		if(x + path[x] <= n && !book[x + path[x]] ) dfs(x + path[x],s+1);  //电梯往上走
		if(x - path[x] >= 1 && !book[x - path[x]] ) dfs(x - path[x],s+1);  //汪下走
		  book[x] = false;  // 回溯
	}
	int main()
	{
	    scanf("%d%d%d",&n,&a,&b);
		for(int i = 1; i <= n; i++)
		  scanf("%d",path+i);
		  book[a] = true;
		  dfs(a,0);
		  if(res !=  inf)
		  printf("%d",res);
		  else printf("-1");
		return 0;
	 } 

5.

题目描述

已知 nn 个整数 x_1,x_2,cdots,x_nx1​,x2​,⋯,xn​,以及 11 个整数 kk(k

3+7+12=223+7+12=22

3+7+19=293+7+19=29

7+12+19=387+12+19=38

3+12+19=343+12+19=34

现在,要求你计算出和为素数共有多少种。

例如上例,只有一种的和为素数:3+7+19=293+7+19=29。

输入格式

第一行两个空格隔开的整数 n,kn,k(1 le n le 201≤n≤20,k

第二行 nn 个整数,分别为 x_1,x_2,cdots,x_nx1​,x2​,⋯,xn​(1 le x_i le 5times 10^61≤xi​≤5×106)。

输出格式

输出一个整数,表示种类数。

输入输出样例

输入 #1复制

4 3
3 7 12 19

输出 #1复制

1
#include 

using namespace std;

int n,k;
int a[30];
int ans;

bool isprime(int x)
{
	if(x < 2)
	 return false;
	 for(int i = 2; i <= x / 2; i++)
	  if(x % i == 0)
	  return false;
	  return true;
}
void dfs(int s,int sum,int x)   // x已经选过数之后的开始的下标 
{
	if(s == k)
	{
		if(isprime(sum))
		ans++;
		return;
	}
	for(int i = x; i < n; i++)
	dfs(s+1,sum+a[i],i+1);
	return;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	 cin >> n >> k;
	 for(int i = 0; i < n; i++)
	  cin >> a[i];
	  dfs(0,0,0); 
	  cout << ans;
	return 0;
}
6.题目描述

Perket 是一种流行的美食。为了做好 Perket,厨师必须谨慎选择食材,以在保持传统风味的同时尽可能获得最全面的味道。你有 nn 种可支配的配料。对于每一种配料,我们知道它们各自的酸度 ss 和苦度 bb。当我们添加配料时,总的酸度为每一种配料的酸度总乘积;总的苦度为每一种配料的苦度的总和。

众所周知,美食应该做到口感适中,所以我们希望选取配料,以使得酸度和苦度的绝对差最小。

另外,我们必须添加至少一种配料,因为没有任何食物以水为配料的。

输入格式

第一行一个整数 nn,表示可供选用的食材种类数。

接下来 nn 行,每行 22 个整数 s_isi​ 和 b_ibi​,表示第 ii 种食材的酸度和苦度。

输出格式

一行一个整数,表示可能的总酸度和总苦度的最小绝对差。

输入输出样例

输入 #1复制

1
3 10

输出 #1复制

7

输入 #2复制

2
3 8
5 8

输出 #2复制

1

输入 #3复制

4
1 7
2 6
3 8
4 9

输出 #3复制

1
#include 
#include 
#include 

using namespace std;

int n;
int a[20][4];
int res = 0x3f3f3f3f;

void dfs(int i ,int s,int k)
{
	if(i == n)
	{
		if(k == 0 && s == 1)  return; //题目要求
		res = min(res,abs(s - k));  // 绝对值最小
	}
	else 
	{
		dfs(i+1,s*a[i][0],k+a[i][1]);  //选
		dfs(i+1,s,k);   // 不选
	}
	return;
}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
      cin >> n;
	  for(int i = 0; i < n; i++)
	    cin >> a[i][0] >> a[i][1];
		dfs(0,1,0); 
		cout << res << endl;   
	return 0;
}
7.题目背景

给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过。给定起点坐标和终点坐标,问: 每个方格最多经过1次,有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式,每次只能移动一个方格。数据保证起点上没有障碍。

题目描述

输入格式

第一行N、M和T,N为行,M为列,T为障碍总数。第二行起点坐标SX,SY,终点坐标FX,FY。接下来T行,每行为障碍点的坐标。

输出格式

给定起点坐标和终点坐标,问每个方格最多经过1次,从起点坐标到终点坐标的方案总数。

输入输出样例

输入 #1复制

2 2 1
1 1 2 2
1 2

输出 #1复制

1
#include 
#include 

using namespace std;

int a[6][6];
bool b[6][6];
int n,m,t;
int sx,sy,ex,ey;
int res = 0;

void dfs(int x,int y)
{
	int nx,ny;
	int ne[4][2] = {{0,1},{1,0},{-1,0},{0,-1}}; //四个方向
	if(x == ex && y == ey)   //到达目标地方
	{
		res++;
		return;
	}
	else
	{
		 for(int i = 0; i < 4; i++)
		   {
		   	nx = x + ne[i][0];
		   	ny = y + ne[i][1];
		   	if(nx < 1 || ny < 1 || nx > n || ny > m)  //判断是否走出了地图范围
		   	 continue;
		   	 if(a[nx][ny] == 0 && b[nx][ny] == false)
		   	 {
		   	      b[x][y] = true;
				  dfs(nx,ny);
			     b[x][y] = false;	
			 }
		   }
	}
	return;
}
int main()
{
    cin >> n >> m >> t;
    cin >> sx >> sy >> ex >> ey;
    for(int i = 1 ; i <= t; i++)
    {
    	int l,r;
    	cin >> l >> r;
    	a[l][r] = 1;
	}
	dfs(sx,sy);
	cout << res << endl;
	return 0; 
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5710852.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存