搜索练习

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

基本概念（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; 
}