西安 餐饮 网站建设,贵阳网站开发工程师招聘网,wordpress插件浏览权限,百度广告竞价排名作者#xff1a;指针不指南吗 专栏#xff1a;蓝桥杯倒计时冲刺 #x1f43e;马上就要蓝桥杯了#xff0c;最后的这几天尤为重要#xff0c;不可懈怠哦#x1f43e; 文章目录1.青蛙跳杯子1.青蛙跳杯子 题目 链接#xff1a; 青蛙跳杯子 - 蓝桥云课 (lanqiao.cn) X 星球的… 作者指针不指南吗 专栏蓝桥杯倒计时冲刺 马上就要蓝桥杯了最后的这几天尤为重要不可懈怠哦 文章目录1.青蛙跳杯子1.青蛙跳杯子 题目 链接 青蛙跳杯子 - 蓝桥云课 (lanqiao.cn) X 星球的流行宠物是青蛙一般有两种颜色白色和黑色。 X 星球的居民喜欢把它们放在一排茶杯里这样可以观察它们跳来跳去。 如下图有一排杯子左边的一个是空着的右边的杯子每个里边有一只青蛙。 WWWBB B 其中W 字母表示白色青蛙B 表示黑色青蛙∗ 表示空杯子。 X 星的青蛙很有些癖好它们只做 3 个动作之一 跳到相邻的空杯子里。隔着 1 只其它的青蛙随便什么颜色跳到空杯子里。隔着 2 只其它的青蛙随便什么颜色跳到空杯子里。 对于上图的局面只要 1 步就可跳成下图局面 WWW ∗BBB 本题的任务就是已知初始局面询问至少需要几步才能跳成另一个目标局面。 输入描述 输入为 2 行2 个串表示初始局面和目标局面。我们约定输入的串的长度不超过 15。 输出描述 输出要求为一个整数表示至少需要多少步的青蛙跳。 输入输出样例 输入 *WWBB
WWBB*输出 2第一次 AC 0% #includebits/stdc.h
using namespace std;typedef pairint,string PII;int cnt;
int d[17];
string st,zz;
int dx[6]{1,-1,2,-2,3,-3};void bfs()
{int kst.size();memset(d,-1,sizeof d);queuePII q;q.push({1,st});d[1]0;while(q.size()){auto tq.front();q.pop();for(int i0;i6;i){int xt.firstd[i];if(x1xk){swap(st[t.first],st[x]);d[x]d[t.first]1;q.push({x,st});if(t.secondzz){coutd[x];return;}}swap(st[t.first],st[x]);}}
}int main()
{cinstzz;bfs();return 0;
}当 队列为空的时候bfs 里面的 还没有 得到最后想要的字符串 正确题解 #include bits/stdc.husing namespace std;
string st_str,end_str;
int n;
int d[6] {-3,-2,-1,1,2,3};
mapstring,int ans;//补全BFS函数,百分之八十都是模板了直接背(狗头)
int bfs()
{//声明一个队列queuestring 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的映射这个方法很可 使用 map的定义 maptypename1,typename2mp; 与其他STL容器在定义上不一样因为map需要确定映射前类型键key和映射后类型值value 所以需要在内填写两个类型其中一个是键的类型第二个是值得类型 如果是int型映射到int型就相当于是普通的int型数组 但是如果是字符串到整型的映射必须是string而不是char数组 mapstring,intmp 这时因为char数组作为数组是不能被作为键值的。所以字符串作映射只能用string 而map的键也可以是STL容器 mapsetint,stringmp map容器内元素的访问 ①通过下标访问 【注意】map的键是唯一的 mp[‘c’]20; ②通过迭代器访问 定义方式与其他STL容器迭代器相同 【不同】 map迭代器的使用方式和其他STL容器的迭代器不同 因为map的每一对映射都有两个typename 这决定了必须通过一个it来同时访问键和值 事实上map可以使用it-first来访问键 使用it-second来访问值 #includebits/stdc.h
using namespace std;
int main()
{ mapchar,intmp; mp[m]20; mp[r]30; mp[a]40; for(mapchar,int::iterator itmp.begin();it!mp.end();it) { printf(%c %d\n,it-first,it-second); } return 0;
}map会以键的大小从小到大的顺序自动排序 即按照amr的顺序排列这三对映射 这是因为map内部是使用红黑树set也是 在建立映射的过程中会自动实现从小到大的排序功能 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() 清空 常见用途 ①需要建立字符或字符串与整数之间影射的题目使用map可以减少代码量 ②判断大整数或者其他类型数据是否存在的题目可以把map当bool数组使用 ③字符串和字符串的映射也有可能会遇到 延伸 map的键和值是唯一的而如果一个键需要对应多个值 就只能用multimap 反思 这个题开始的时候有想到 递推但是青蛙跳的情况有六种情况很难实现代码 所以使用 BFS 以六种方式来扩展 不断的进行交换当 stzz 即跳成我们想要的结果时返回 我们需要记录每次交换之后的string 和位置和第几次跳三个值都需要记录 第几次 跳 他不能6种情况每种情况ans就 可以 让他 和 string 进行组合就ok 这个题 复习了 map理清楚每个变量之间的关系以及怎么去储存他更加理解 BFS 没思路就是用 bfs
