最短步数的问题就是关于的不同状态之间的转化,整体思路跟最短路差不多,只不过这里对状态的操作比较麻烦,还有一点需要注意,因为这样的题不好计算转化的次数,所以最好用stl容器来实现,不然可能会爆错…
以该题为例
三种状态转化的方式,我们可以用string自带的一些函数来实现
A:交换两行,那么我们首先要把第一行第二行的元素找出来,然后我们要先将t2反向再把t1反向,这个时候t = t1 + t2(可以自己画一画)
string mov0(string t)
{
string t1(t, 0, 4);
string t2(t, 4, 4);
reverse(t2.begin(), t2.end());
t = t2;
reverse(t1.begin(), t1.end());
t += t1;
return t;
}
B:
string mov1(string t)
{
string t1(t, 0, 4);
string t2(t, 4, 4);
t1.insert(t1.begin(), t1[3]);
t1.pop_back();
reverse(t2.begin(), t2.end());
t2.insert(t2.begin(), t2[3]);
t2.pop_back();
t = t1;
reverse(t2.begin(), t2.end());
t += t2;
return t;
}
C
string mov2(string t)
{
string t1(t, 0, 4);
string t2(t, 4, 4);
char s = t1[1];
reverse(t2.begin(), t2.end());
t1[1] = t2[1];
t2[1] = t2[2];
t2[2] = t1[2];
t1[2] = s;
t = t1;
reverse(t2.begin(), t2.end());
t += t2;
return t;
}
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
using namespace std;
unordered_map<string, int> mp;
unordered_map<string, char> q;
unordered_map<string, string> st;
string que[100000];// 因为这里不好计算状态数量,所以最好使用stl
string mov0(string t)
{
string t1(t, 0, 4);
string t2(t, 4, 4);
reverse(t2.begin(), t2.end());
t = t2;
reverse(t1.begin(), t1.end());
t += t1;
return t;
}
string mov1(string t)
{
string t1(t, 0, 4);
string t2(t, 4, 4);
t1.insert(t1.begin(), t1[3]);
t1.pop_back();
reverse(t2.begin(), t2.end());
t2.insert(t2.begin(), t2[3]);
t2.pop_back();
t = t1;
reverse(t2.begin(), t2.end());
t += t2;
return t;
}
string mov2(string t)
{
string t1(t, 0, 4);
string t2(t, 4, 4);
char s = t1[1];
reverse(t2.begin(), t2.end());
t1[1] = t2[1];
t2[1] = t2[2];
t2[2] = t1[2];
t1[2] = s;
t = t1;
reverse(t2.begin(), t2.end());
t += t2;
return t;
}
void bfs(string start, string end)
{
int hh = 0, tt = 0;
que[tt++] = start;
mp[start] = 0;
if(start == end) return ;
while (hh < tt)
{
string t = que[hh++];
for (int i = 0; i < 3; i++)
{
string k;
if (i == 0)
{
k = mov0(t);
}
else if (i == 1)
{
k = mov1(t);
}
else
k = mov2(t);
if (mp[k] || k == start)
continue;
que[tt++] = k;
st[k] = t;
mp[k] = mp[t] + 1;
if (i == 0)
q[k] = 'A';
else if (i == 1)
q[k] = 'B';
else
q[k] = 'C';
if (k == end)
{
return;
}
}
}
}
int main()
{
string end;
string start("12345678");
for(int i = 0; i < 8; i ++)
{
int x;
cin >> x;
end += x + '0';
}
bfs(start, end);
cout << mp[end] << endl;
if(start != end)
{
string t;
for(string i = end; i != start; i = st[i])
{
t.push_back(q[i]);
}
reverse(t.begin(), t.end());
cout << t << endl;
}
return 0;
}