【蓝桥杯每日一题】4.10搜索练习

蓝桥杯就要来咯，加油！

T1:

题目来源：
3472. 八皇后 - AcWing题库

• 简单的八皇后问题，唯一注意点在于怎么存放数值

#include<bits/stdc++.h>
using namespace std;

int a[8][8];
int n,b;
char s[8];  //字符串形式好存放，不用在*10+了
int res[100]; //由于存放解法数据
bool col[20],dui[20],fandui[20];
int id=0;

void dfs(int m)
{
	if(m==8){
		res[++id]=atoi(s);
		return ;
	}
	for(int i=0;i<8;i++)
	{
		if(!col[i]&&!dui[m+i]&&!fandui[8-m+i])
		{
			s[m]=i+1+'0'; //第u个皇后所在的位置
			col[i]=dui[m+i]=fandui[8-m+i]=true; //标记列、对角线、反对角线
			dfs(m+1);
			col[i]=dui[m+i]=fandui[8-m+i]=false;
		}
	}
}
int main(){
	
	dfs(0);
	scanf("%d",&n);
	
	while(n--)
	{
		scanf("%d",&b);
		printf("%d\n",res[b]);
	}
	
	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

T2：

3699. 树的高度 - AcWing题库

DFS：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;

int n,m;
int res;
vector<int> a[N]; //其实算是一个二维数组，每行存放相连的节点ID，相比更加省空间
bool vis[N];

void dfs(int depth,int k)
{
	res=max(res,depth);
	
	for(auto i: a[k])
	{
		if(!vis[i])
		{
			vis[i]=1;dfs(depth+1,i);
		}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	
	while(n--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		a[x].push_back(y);	 //无向边
		a[y].push_back(x);
	}
	vis[m]=1;
	dfs(0,m);
	
	printf("%d",res);	
	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

BFS：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int m, n;
int dep[N];
vector<int> a[N];
int res = 0;

void bfs() 
{
    queue<int> q;
    q.push(m);
    dep[m] = 0;
    while (!q.empty()) 
	{
        int u = q.front();
        q.pop();
        
        for (int i=0;i<a[u].size();i++) 
		{
            int v = a[u][i];
            
            //特判防止根节点被计算
            if(v==m)continue;
            if (!dep[v])
			{
				dep[v] = dep[u] + 1;
				res=max(res,dep[v]);
				q.push(v);
			}
        }
    }
}


int main() 
{
    scanf("%d%d",&n,&m);

	while(n--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		a[x].push_back(y);	 //无向边
		a[y].push_back(x);
	}
	
    bfs();
   	printf("%d",res);
    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
46
47
48
49
50
51