第八届蓝桥杯（软件类）C++省赛A组真题题解

文章目录

• 题目链接
• A组真题
• • 题目结构
  • 第一题 迷宫
  • 第二题 跳蚱蜢
  • 第三题 魔方状态
  • 第四题 方格分割
  • 第五题 字母组串
  • 第六题 最大公共子串
  • 第七题 正则问题
  • 第八题 包子凑数
  • 第九题 分巧克力
  • 第十题 油漆面积

题目链接

A组真题

题目结构

第一题 迷宫

• 问题重现

  X星球的一处迷宫游乐场建在某个小山坡上。
  它是由10×10相互连通的小房间组成的。

  房间的地板上写着一个很大的字母。
  我们假设玩家是面朝上坡的方向站立，则：
  L表示走到左边的房间，
  R表示走到右边的房间，
  U表示走到上坡方向的房间，
  D表示走到下坡方向的房间。

  X星球的居民有点懒，不愿意费力思考。
  他们更喜欢玩运气类的游戏。这个游戏也是如此！

  开始的时候，直升机把100名玩家放入一个个小房间内。
  玩家一定要按照地上的字母移动。

  迷宫地图如下：

  UDDLUULRUL
  UURLLLRRRU
  RRUURLDLRD
  RUDDDDUUUU
  URUDLLRRUU
  DURLRLDLRL
  ULLURLLRDU
  RDLULLRDDD
  UUDDUDUDLL
  ULRDLUURRR

  请你计算一下，最后，有多少玩家会走出迷宫br> 而不是在里边兜圈子。

  注意

  请提交该整数，表示走出迷宫的玩家数目，不要填写任何多余的内容。

  如果你还没明白游戏规则，可以参看一个简化的4×4迷宫的解说图：
  

  • 答案

    $31$

  ---

  第二题 跳蚱蜢

  • 问题重现

    如图所示：
    

    

    有9只盘子，排成1个圆圈。
    其中8只盘子内装着8只蚱蜢，有一个是空盘。
    我们把这些蚱蜢顺时针编 为 1~8

    每只蚱蜢都可以跳到相邻的空盘中，
    也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。

    请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列，
    并且保持空盘的位置不变（也就是1-8换位，2-7换位,…），至少要经过多少次跳跃/p>

    注意

    要求提交的是一个整数，请不要填写任何多余内容或说明文字。

  • 解题思路

    对于这道题，==我们需要将空格作为一个动点，它可以进行四种操作，由于我们需要寻找最少的操作次数，所以我们可以利用$bfs$模拟交换。==为了避免状态重复我们可以利用$map$容器来实现，记录已经出现过的地图状态。值得注意的一点就是坐标的处理 ，我们如果坐标大于$8$就需要对$8$取余，而如果小于$0$，则需要加上$9$这样才可以保证逻辑上是环状的。

  • 代码

  /**  *@filename:跳蚱蜢  *@author: pursuit  *@CSDNBlog:unique_pursuit  *@email: 2825841950@qq.com  *@created: 2021-03-26 10:46**/#include using namespace std;typedef long long ll;const int maxn = 100000 + 5;const int mod = 1e9+7;mapstring,int> p;//存储访问过的状态。//将空格作为动点。由于要寻找最少跳跃，我们需要进行bfs。struct node{    int x;    int step;    string graph;//记录当前状态的地图。};string res;string result="087654321";void bfs(){    node head,temp;    queuenode> q;    head.x=0,head.step=0,head.graph=res;    p[head.graph]++;    q.push(head);    while(!q.empty()){head=q.front();q.pop();//接下来开始模拟四种操作。if(head.graph==result){    couthead.stependl;    return;}for(int i=0;i4;i++){    if(i==0){ //左跳。 temp.x=head.x+1; //此时需要判断temp坐标是否符合。 if(temp.x>8){temp.x=0; }    }    else if(i==1){ //跨越跳。 temp.x=head.x+2; if(temp.x>8){temp.x=(temp.x-1)%8; }    }    else if(i==2){ temp.x=head.x-1; if(temp.x0){temp.x=8; }    }    
  声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！