最小步数模型

跟传统网格bfs不同,每个状态是一个网格,状态为棋盘到棋盘间,构成有向图,求有向图的最短路径

魔板

每个点可以由操作A、B、C向三个方向扩展,以整个魔板为状态,容易想到通过bfs,从satrt开始扩展到end,每个状态可以有3个扩展方向。

如何保证序列字典序最小:由于每个状态的操作序列不同,若存在end,只需要按照A、B、C顺序扩展,就一定有字典序最小的序列。(下图三叉树解释)

如图所示,每个状态三条分支,当分支有交叉时,此状态一定由更小的操作数先转移过,因此可以保证字典序最小。

CODE
求路径

while(end != start)
    {
        res += pre[end].first;
        end = pre[end].second;
    }

完整代码

#include<iostream>
#include<unordered_map>
#include<algorithm>
#include<queue>
using namespace std;

int g[2][4];
unordered_map<string,int> dist;
unordered_map<string,pair<char,string>> pre;

void set(string s)
{
    for(int i = 0;i < 4;i++) g[0][i] = s[i];
    for(int j = 4,i = 3;j < 8;i--,j++) g[1][i] = s[j];
}

string get()
{
    string res;
    for(int i = 0;i < 4;i++) res += g[0][i];
    for(int i = 3;i >= 0;i--) res += g[1][i];
    return res;
}

string workA(string s)
{
    set(s);
    for(int i = 0;i < 4;i++) swap(g[0][i],g[1][i]);
    return get();
}

string workB(string s)
{
    set(s);
    char a = g[0][3],b = g[1][3];
    for(int i = 3;i >= 1;i--) 
    {
        g[0][i] = g[0][i-1];
        g[1][i] = g[1][i-1];
    }
    g[0][0] = a,g[1][0] = b;
    return get();
}

string workC(string s)
{
    set(s);
    char v = g[0][1];
    g[0][1] = g[1][1];
    g[1][1] = g[1][2];
    g[1][2] = g[0][2];
    g[0][2] = v;
    
    return get();
}

int bfs(string start,string end)
{
    if(start == end) return 0;
    
    dist[start] = 0;
    
    queue<string> q;
    q.push(start);
    
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        
        string m[3];
        m[0] = workA(t);
        m[1] = workB(t);
        m[2] = workC(t);
        
        for(int i = 0;i < 3;i++)
        {
            if(dist[m[i]] == 0)
            {
                dist[m[i]] = dist[t] + 1;
                pre[m[i]] = {'A' + i,t};
                q.push(m[i]);
                if(m[i] == end) return dist[end];
            }
        }
    }
    return -1;
}
int main()
{
    string start = "12345678",end;
    for(int i = 0;i < 8;i++)
    {
        int x;cin>>x;
        end += x + '0';
    }
    
    int step = bfs(start,end);
    
    cout<<step<<endl;
    
    if(step)
    {
        string res;
        while(end != start)
        {
            res += pre[end].first;
            end = pre[end].second;
        }
        reverse(res.begin(),res.end());
        cout<<res<<endl;
    }
    return 0;
}