首页分享蓝桥杯2017年第八届真题

蓝桥杯2017年第八届真题

来源：萌宠菠菠乐园时间：2024-11-14 06:14

题目

X星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。
X星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。
如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。

*WWWBBB

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

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

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

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

WWW*BBB

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

输入为2行，2个串，表示初始局面和目标局面。
输出要求为一个整数，表示至少需要多少步的青蛙跳。

输入
输入为2行，2个串，表示初始局面和目标局面。

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

样例输入

*WWBB WWBB* 12

样例输出

2 1

解题思路

本题是一道变化前后对应的题目，是典型的广度优先搜索的题目，类似的题目有题目 1426: 蓝桥杯历届试题-九宫重排。

广度优先搜索的基本思路是：建立一个队列，将初始状态的字符串存入其中，再建立一个map，存储变换到每一个字符串需要几次变换，以及该字符串是否曾经出现过。

不断对队列中最前面的字符串进行变换，若变换后的字符串和结果一致，输出该字符串在map中对应的所需变换次数；若不一致，则判断该字符串是否出现过，若未出现过，则存入队列且在map中存储相应的变换次数。

代码

#include<bits/stdc++.h> using namespace std; queue <string> q; map <string,int> maps; string a,b; int steps; void BFS(){ int i,len,sub_empty;//sub_empty空位的下标 int sc,F = 0;//是否找到一致的 while (!q.empty()){ string d,c = q.front(); q.pop();//出队 len = c.size(); sc = maps[c]; for (i=0;i<c.size();i++)//找到空位 if (c[i]=='*') break; sub_empty = i; for (i=sub_empty-3;i<=(sub_empty+3);i++) { if (i>-1 && i!=sub_empty && i<len)//防止下标越界 { d = c; d[sub_empty] = c[i]; d[i] = c[sub_empty];//交换位置即表示跳跃 if (d==b)//符合了 { F = 1; steps = sc+1; break; } if (maps[d]==0)//未出现过 { q.push(d); maps[d] = sc+1; } } } if (F==1) break; } } int main() { cin >> a >> b; q.push(a);//入队 maps[a] = 0; if (a==b) printf("0"); else { BFS(); printf("%d",steps); }return 0; }

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859

网址: 蓝桥杯2017年第八届真题 https://www.mcbbbk.com/newsview552520.html

所属分类：萌宠日常