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