搜素题目（蓝桥杯 C++ 代码+注解）

目录

题目一（小朋友崇拜圈）：

代码：

题目二（穿越雷区）：

代码： 

 题目三（分考场）：

代码：

 题目四（受伤的皇后）：

代码：

题目一（小朋友崇拜圈）：

代码：

#include
using namespace std;
int a[100010];
int ans = 0, t;
int book[100010];
void dfs(int k,int sum)
{
	if (book[k])//已经访问过，则有可能为环
	{
		if (k==t)//回到起始，则为环
			if (sum > ans)
		        ans = sum;
		return;
	}
	book[k] = 1;//标记已经访问
	dfs(a[k], sum + 1);
	book[k] = 0;//回溯
}
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++)
	{
		t = i;
		dfs(i, 0);//从第i个人出发可以组成0个人的圈
	}
	cout << ans;
}

题目二（穿越雷区）：

代码： 

#include
#include
using namespace std;
char s[110][110];
int book[110][110] = { 0 };
int ans = 0;
int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };
int flag = 0;//标志是否能走通
int n;
typedef struct node
{
	int x, y, s;
}node;
node start, end1;
queue q;
int check(int x, int y)//走到终点
{
	if (x == end1.x && y == end1.y)
		return 1;
	return 0;
}
void bfs()
{
	while (!q.empty())
	{
		int x = q.front().x, y = q.front().y;
		int step = q.front().s;//走到该点需要的步数
		q.pop();
		if (check(x, y))
		{
			flag = 1;
			cout << step;
			break;
		}
		for (int k = 0; k < 4; k++)
		{
			int tx = x + dx[k], ty = y + dy[k];
			if (tx<1 || tx>n || ty<1 || ty>n || book[tx][ty]==1)//是否越界，是否走过
				continue;
			else if (s[x][y]=='A'||(s[x][y] == '+' && s[tx][ty] == '-')||s[tx][ty]=='B')//符合上一步和这一步为不同符号，起点，终点不算
			{
				q.push({ tx, ty, step + 1 });
				book[tx][ty] = 1;
			}
			else if (s[x][y]=='A'||(s[x][y] == '-' && s[tx][ty] == '+')||s[tx][ty]=='B')
			{
				q.push({ tx, ty, step + 1 });
				book[tx][ty] = 1;
			}
		}
	}
 
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> s[i][j];
			if (s[i][j] == 'A')
				start.x = i, start.y = j;
			else if (s[i][j] == 'B')
				end1.x = i, end1.y = j;
		}
	}
	q.push({ start.x,start.y,0 });
	bfs();
	if (flag == 0)
		cout << "-1";
}

 题目三（分考场）：

代码：

#include
#include
#include//两种可能，一种加在原有的考场中，一种自己单独开一个考场
using namespace std;
const int N=200;
int st[N][N];
int mp[N][N];//第i个考场的第i位同学
int n,m;
int minkey;
void dfs(int k,int res)//第k个同学，存在res个考场
{
  if(res>=minkey)return;//目前的考场数大于了最优考场数，不再继续
  if(k>n)//目前遍历的是n+1位同学，没有，已经遍历完了
  {
    minkey=min(minkey,res);//更新考场数
    return ;
  }
  for(int i=1;i<=res;i++)//依次遍历每个考场，看有没有认识他的
  {
    int u=1;
      while(mp[i][u]&&!st[k][mp[i][u]])//如果第i个考场的第u名同学存在且不认识，继续往后遍历
        u++;
        //注意这个u如果每个人都不认识的话，这个u代表的是本考场人数加一
        //那么这个考场就没有第u个人,
        if(!mp[i][u])//没有第u个，让第k个同学成为第u个
        {
          mp[i][u]=k;
          dfs(k+1,res);
          mp[i][u]=0;//回溯
        }
      
  }
  //自己新加一个考场
  mp[res+1][1]=k;
  dfs(k+1,res+1);
  mp[res+1][1]=0;
}
int main()
{
  cin>>n>>m;
  minkey=n;
  while(m--)
  {
    int a,b;
    cin>>a>>b;
    st[a][b]=1;//表示ab认识
    st[b][a]=1;
  }
  dfs(1,0);//第1个同学有0个考场
  cout<
  return 0;
}

 题目四（受伤的皇后）：

代码：

#include 
using namespace std;
int a[15];
int ans = 0;
int n;
int check(int a)//判断是否继续摆
{
    if (a > n)//大于最大行数，即摆完，方法加一
    {
        ans++;
        return 1;
    }
    else
        return 0;
}
int judge(int k)//判断是否可以摆
{
    for (int i = 1; i < k; i++)
    {
        if (((abs(k - i) == abs(a[k] - a[i]))&&((k-i)<=3))||(a[k] == a[i]))//同一列和斜线
            return 0;//同一斜线说明斜率为1或者-1，则x1-x2/y1-y2=1,即x1-x2=y1-y2同时行号差三以上则不用考虑是否在同一斜线
    }
    return 1;
}
void dfs(int k)
{
    if (check(k))
        return;
    else
    {
        for (int i = 1; i <= n; i++)//遍历每一列
        {
            a[k] = i;
            if (judge(k))
                dfs(k + 1);
            else
                continue;
        }
    }
}
int main()
{
    cin >> n;
    dfs(1);
    cout << ans;
}