藍橋杯-試題 歷屆試題 青蛙跳杯子
問題描述
X星球的流行寵物是青蛙，一般有兩種顏色：白色和黑色，
X星球的居民喜歡把它們放在一排茶杯里，這樣可以觀察它們跳來跳去，
如下圖，有一排杯子，左邊的一個是空著的，右邊的杯子，每個里邊有一只青蛙，
*WWWBBB
其中，W字母表示白色青蛙，B表示黑色青蛙，*表示空杯子，
X星的青蛙很有些癖好，它們只做3個動作之一：
1. 跳到相鄰的空杯子里，
2. 隔著1只其它的青蛙（隨便什么顏色）跳到空杯子里，
3. 隔著2只其它的青蛙（隨便什么顏色）跳到空杯子里，
對于上圖的局面，只要1步，就可跳成下圖局面：
WWW*BBB
本題的任務就是已知初始局面，詢問至少需要幾步，才能跳成另一個目標局面，
輸入為2行，2個串，表示初始局面和目標局面，
輸出要求為一個整數，表示至少需要多少步的青蛙跳，
樣例輸入
樣例輸出
2
樣例輸入
樣例輸出
10
資料規模和約定
我們約定，輸入的串的長度不超過15
資源約定：
峰值記憶體消耗（含虛擬機） < 256M
CPU消耗 < 1000ms
請嚴格按要求輸出，不要畫蛇添足地列印類似：“請您輸入…” 的多余內容，
所有代碼放在同一個源檔案中，除錯通過后，拷貝提交該原始碼，
不要使用package陳述句，不要使用jdk1.7及以上版本的特性，
主類的名字必須是：Main，否則按無效代碼處理，
----------------------------
笨笨有話說：
我夢見自己是一棵大樹，
青蛙跳躍，
我就發出新的枝條，
春風拂動那第 5 層的新枝,
哦，我已是枝繁葉茂，
**
題解思路：
BFS的題目，根據題意，只有空杯子兩邊的各3只青蛙才能夠跳入空杯子，距離空杯子超過三個杯子的青蛙不能跳進空杯，所以，對每種現在的狀況，分別將每個可以跳進空杯子的青蛙跳進空杯子形成一種狀態，如果和目標狀態相同，則退出函式，輸出步數，否則，入隊，如過空瓶子左右三格子共有6只青蛙，則一共會形成6種狀態入隊，（用map將每種入過隊的狀態設定成true，保證每種狀態只訪問一遍，否則會超時）；題目要求輸出步數，所以用一個結構體，保存當前狀態和已經操作的步數，
**
AC代碼：
#include<iostream>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;
map<string,bool> m; //map來記錄某個狀態是否出現過，初始化所有狀態為false，第一次出現就賦值為true，以防止多次訪問同一個狀態
string s1,s2;//s1為初始狀態，s2為目標狀態，
struct node
{
string s;//該節點狀態
int step;//用來記錄步數
node()
{
step=0;//初始化
}
}temp;
void BFS()//廣度優先搜索
{
if(s1==s2)//如果一開始初始串與目標串一樣，直接輸出步數為0，結束
{
cout<<"0"<<endl;
return;
}
m[s1]=true;//標記初始串的狀態已經被訪問過
queue<node> q;//狀態佇列
temp.step=0;//初始步數為0，其實這一步多余，因為在結構體內部已經讓step為0了
temp.s=s1;
q.push(temp);//將初始狀態入列
while(!q.empty())
{
node top=q.front();//取出隊首元素
q.pop();
string s=top.s;
temp.step=top.step+1;//進行一次狀態改變，步數加一
for(int j=0;j<s.size();j++)//用j變數來找到空瓶子對應的字串位置
if(s[j]=='*')
for(int i=0;i<s.size();i++)
{
if(i!=j && abs(i-j)<=3)//如果標號為 i 的青蛙可以跳入空瓶子，進行操作
{
string s3=s;//用s3來保存下一個狀態，不能動s，因為后續的多種狀態都來源于s
swap(s3[i],s3[j]);
if(s3==s2)//如果交換后是目標狀態，結束
{
cout<<temp.step<<endl;
return;
}
if(m[s3]==false)//如果這個狀態還沒出現過，入隊
{
temp.s=s3;
q.push(temp);
m[s3]=true;
}
}
}
}
}
int main()
{
cin>>s1>>s2;
BFS();
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/261460.html
標籤：其他
上一篇：洛谷P3150 pb的游戲（1）