仿照提高课里的魔板那道题写出的
C++ 代码
#include<bits/stdc++.h>
using namespace std;
unordered_set<string> st;
unordered_map<string,pair<string,char>> pre;
string start,en;
queue<string> q;
char num[3][3];
pair<int,int> x;
void ser(string s)
{
int k=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
num[i][j]=s[k++];
}
string get()
{
string p;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
p+=num[i][j];
return p;
}
void get_num()
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if(num[i][j]=='x')
{
x.first=i;
x.second=j;
}
}
string u(string s)
{
ser(s);
get_num();
if(x.first!=0)
{
swap(num[x.first][x.second],num[x.first-1][x.second]);
return get();
}
return "fa";
}
string d(string s)
{
ser(s);
get_num();
if(x.first!=2)
{
swap(num[x.first][x.second],num[x.first+1][x.second]);
return get();
}
return "fa";
}
string l(string s)
{
ser(s);
get_num();
if(x.second!=0)
{
swap(num[x.first][x.second],num[x.first][x.second-1]);
return get();
}
return "fa";
}
string r(string s)
{
ser(s);
get_num();
if(x.second!=2)
{
swap(num[x.first][x.second],num[x.first][x.second+1]);
return get();
}
return "fa";
}
bool bfs(string start,string en)
{
if(start==en) return true;
st.insert(start);
q.push(start);
while(q.size())
{
auto t=q.front();
q.pop();
string s[4];
s[0]=u(t);
s[1]=d(t);
s[2]=l(t);
s[3]=r(t);
for(int i=0;i<4;i++)
{
auto m=s[i];
if(s[i]!="fa"&&st.count(m)==0)
{
q.push(m);
st.insert(m);
pre[m].first=t;
if(i==0) pre[m].second='u';
if(i==1) pre[m].second='d';
if(i==2) pre[m].second='l';
if(i==3) pre[m].second='r';
}
}
if(t==en) return true;
}
return false;
}
int main()
{
getline(cin,start);
while(start.find(' ')!=string::npos)
{
start.erase(start.find(' '),1);
}
for(int i=1;i<=8;i++) en+=i+'0';
en+='x';
bool k=bfs(start,en);
if(k==false)
{
cout<<"unsolvable";
return 0;
}
string res;
while(start!=en)
{
res+=pre[en].second;
en=pre[en].first;
}
reverse(res.begin(),res.end());
for(auto i:res) cout<<i;
return 0;
}