AcWing 1107. 1107.魔板
原题链接
简单
作者:
_Airヾ梦及丨
,
2021-10-27 17:50:51
,
所有人可见
,
阅读 191
C++ 代码,第一次做此题时写的,挺好理解的bfs。。
#include <bits/stdc++.h>
using namespace std;
string start;
string endd;
unordered_map<string,int> mp;
int flag=0;
unordered_map<string,string> ans;
set<string> s;
void bfs(string start)
{
queue<string> q;
q.push(start);
ans[start]="";
while(!q.empty())
{
string t=q.front();
q.pop();
int temp=mp[t];
if(t==endd&&flag==0)
{
flag=1;
cout <<mp[t]<<endl;
s.insert(ans[t]);
}
else if(t==endd&&flag==1)
{
s.insert(ans[t]);
}
string tt=t;
reverse(tt.begin(),tt.end());
if(!mp.count(tt))
{
mp[tt]=temp+1;
q.push(tt);
ans[tt]=ans[t]+"A";
}
tt="";
tt+=t.substr(0,3);
tt+=t.substr(5,3);
tt.insert(0,1,t[3]);
tt+=t[4];
if(!mp.count(tt))
{
mp[tt]=temp+1;
q.push(tt);
ans[tt]=ans[t]+"B";
}
tt="";
tt+=t.substr(0,1)+t.substr(6,1)+t.substr(1,1)+t.substr(3,1)+t.substr(4,1)+t.substr(2,1)+t.substr(5,1)+t.substr(7,1);
if(!mp.count(tt))
{
mp[tt]=temp+1;
q.push(tt);
ans[tt]=ans[t]+"C";
}
}
set<string>::iterator it = s.begin();
cout <<*it;
}
int main()
{
ios::sync_with_stdio(false);
start="12345678";
for(int i=0;i<8;i++)
{
char c;
cin >> c;
endd+=c;
}
if(start==endd)
{
cout <<"0";
return 0;
}
bfs(start);
return 0;
}