蓝桥杯刷题冲刺 | 倒计时16天

作者：指针不指南吗
专栏：蓝桥杯倒计时冲刺

🐾马上就要蓝桥杯了，最后的这几天尤为重要，不可懈怠哦🐾

1.青蛙跳杯子

• 题目

  链接： 青蛙跳杯子 - 蓝桥云课 (lanqiao.cn)

  X 星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。

  X 星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。

  如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。

  WWWBB B

  其中，W 字母表示白色青蛙，B 表示黑色青蛙，∗ 表示空杯子。

  X 星的青蛙很有些癖好，它们只做 3 个动作之一：

  1. 跳到相邻的空杯子里。
  2. 隔着 1 只其它的青蛙（随便什么颜色）跳到空杯子里。
  3. 隔着 2 只其它的青蛙（随便什么颜色）跳到空杯子里。

  对于上图的局面，只要 1 步，就可跳成下图局面：

  WWW ∗BBB

  本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。

  输入描述

  输入为 2 行，2 个串，表示初始局面和目标局面。我们约定，输入的串的长度不超过 15。

  输出描述

  输出要求为一个整数，表示至少需要多少步的青蛙跳。

  输入输出样例

  输入

  *WWBB
  WWBB*
  

  输出

  2
  

• 第一次 AC 0%

  #include<bits/stdc++.h>
  using namespace std;typedef pair<int,string> PII;int cnt;
  int d[17];
  string st,zz;
  int dx[6]={1,-1,2,-2,3,-3};void bfs()
  {int k=st.size();memset(d,-1,sizeof d);queue<PII> q;q.push({1,st});d[1]=0;while(q.size()){auto t=q.front();q.pop();for(int i=0;i<6;i++){int x=t.first+d[i];if(x>=1&&x<=k){swap(st[t.first],st[x]);d[x]=d[t.first]+1;q.push({x,st});if(t.second==zz){cout<<d[x];return;}}swap(st[t.first],st[x]);}}
  }int main()
  {cin>>st>>zz;bfs();return 0;
  }
  

  当 队列为空的时候，bfs 里面的 还没有 得到最后想要的字符串

• 正确题解

  #include <bits/stdc++.h>using namespace std;
  string st_str,end_str;
  int n;
  int d[6] = {-3,-2,-1,1,2,3};
  map<string,int> ans;//补全BFS函数,百分之八十都是模板了，直接背(狗头)
  int bfs()
  {//声明一个队列queue<string> q;//将当前的状态入队q.push(st_str);ans[st_str] = 0;//当队列不为空的时候while(q.size()){//取出队头string ss = q.front();q.pop();int cnt = ans[ss];int x = ss.find('*');//拓展六个方向for(int i = 0;i < 6;i++){int z = x + d[i];//判断出来的距离，是合法的if(z>= 0 && z < n){swap(ss[x],ss[z]); //交换青蛙和当前空杯子的位置if(!ans.count(ss)) //用count来判断当前字符串是否在哈希表中出现过{ans[ss] = cnt + 1;//符合结果，输入if(ss == end_str) return ans[ss];q.push(ss);}//还原现场swap(ss[x],ss[z]);}}}return -1;
  }int main()
  {cin >> st_str >>end_str;n = st_str.size();cout << bfs() <<endl;return 0;
  }
  

• map知识点补充

  • 简介

    map翻译为映射，也是常见的STL容器

    在定义数组时（如int array[100]），其实是定义了一个从int型到int型的映射，比如array[0]=25、array[4]=36就分别是将0映射到25、将4映射到36，但是，无论是什么类型它总是将int型映射到其他类型；

    这似乎表现出一个弊端：当需要以其他类型为关键字来做映射时，会显得不太方便，例如有一本字典，上面提供了很多的字符串和对应的页码，如果要用数组来表示“字符串——>页码”这样的对应关系，就会感觉不太好操作，这时，就可以用到map，因为map可以将任何基本类型（包括STL容器）映射到任何基本类型（包括STL容器），也就可以建立string型到int型的映射

    【另一种情况】

    需要判断给定的一些数字在某个文件中是否出现过

    按照正常的思路，可以开一个bool 型hashTable[max_size]，通过判断hashTable[x]为true还是false来确定x是否在文件中出现；

    但是这会碰到一种问题：如果这些数字很大（例如有几千位）那么这个数字就会开不了

    而这时map就可以派上用场，因为可以把这些数字当成一些字符串，然后建立至int的映射（或者直接建立int至int的映射）这个方法很可

  • 使用

  1. map的定义

     map<typename1,typename2>mp;

     与其他STL容器在定义上不一样，因为map需要确定映射前类型（键key）和映射后类型（值value）

     所以需要在<>内填写两个类型，其中一个是键的类型，第二个是值得类型

     如果是int型映射到int型，就相当于是普通的int型数组

     但是如果是字符串到整型的映射，必须是string而不是char数组

     map<string,int>mp

     这时因为char数组作为数组是不能被作为键值的。所以字符串作映射，只能用string

     而map的键也可以是STL容器

     map<set<int>,string>mp

  2. map容器内元素的访问

     ①通过下标访问

     【注意】map的键是唯一的

     mp[‘c’]=20;

     ②通过迭代器访问

     定义方式与其他STL容器迭代器相同

     【不同】

     map迭代器的使用方式和其他STL容器的迭代器不同

     因为map的每一对映射都有两个typename

     这决定了必须通过一个it来同时访问键和值

     事实上，map可以使用it->first来访问键

     使用it->second来访问值

     #include<bits/stdc++.h>
     using namespace std;
     int main()
     {   map<char,int>mp;   mp['m']=20;   mp['r']=30;   mp['a']=40;   for(map<char,int>::iterator it=mp.begin();it!=mp.end();it++)   {       printf("%c %d\n",it->first,it->second);   }   return 0;
     }
     

     map会以键的大小从小到大的顺序自动排序

     即按照a<m<r的顺序排列这三对映射

     这是因为map内部是使用红黑树（set也是）

     在建立映射的过程中会自动实现从小到大的排序功能

  3. map常用函数

     ①find（）

     find(key)返回键是key的映射的迭代器

     ②erase（）

     (1)删除单个元素

     a.mp.erase(it),it为需要删除的元素的迭代器

     b.mp.erase(key),key为欲删除的映射的键

     e.g.mp.erase(‘c’);

     (2)删除一个区间内的所有元素

     还是左闭右开

     (3)size()

     用来获得map中映射的次数

     (4)clear()

     清空

  4. 常见用途

     ①需要建立字符（或字符串）与整数之间影射的题目，使用map可以减少代码量

     ②判断大整数或者其他类型数据是否存在的题目，可以把map当bool数组使用

     ③字符串和字符串的映射也有可能会遇到

     延伸：

     map的键和值是唯一的，而如果一个键需要对应多个值

     就只能用multimap

• 反思

  这个题开始的时候，有想到 递推，但是青蛙跳的情况有六种情况，很难实现代码

  所以使用 BFS ，以六种方式来扩展， 不断的进行交换，当 st==zz 即跳成我们想要的结果时，返回

  我们需要记录，每次交换之后的string ，和位置，和第几次跳，三个值都需要记录

  第几次 跳 他不能，6种情况，每种情况，ans就 ++

  可以 让他 和 string 进行组合，就ok

  • 这个题 复习了 map
  • 理清楚每个变量之间的关系，以及怎么去储存他
  • 更加理解 BFS ，没思路就是用 bfs