奉上原题链接

原题链接

题解集合

火热更新中

知识点

1.字符串读入后转换为数组
2.像使用数组一样使用map（数组是特殊的map/笑）
3.用队列实现bfs扩展最短路

cpp 代码(详解见后文)

#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

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

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

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 move0(string state)
{
    set(state);
    for(int i = 0; i < 4;i ++) swap(g[0][i],g[1][i]);
    return get();
}

string move1(string state)
{
    set(state);
    int v0 = g[0][3], v1 = g[1][3];
    for(int i = 3;i >= 0; i--)
    {
        g[0][i] = g[0][i - 1];
        g[1][i] = g[1][i - 1];
    }
    g[0][0] = v0, g[1][0] = v1;
    return get();
}

string move2(string state)
{
    set(state);
    int 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;

    queue<string> q;
    q.push(start);
    dist[start] = 0;

    while(!q.empty())
    {
        auto t = q.front();
        q.pop();

        string m[3];
        m[0] = move0(t);
        m[1] = move1(t);
        m[2] = move2(t);

        for(int i = 0; i < 3 ; i++)
          if(!dist.count(m[i]))//unused ???
          {
              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()
{
    int x;
    string start, end;
    for(int i = 0;i < 8;i ++)
    {
        cin >> x;
        end +=char(x + '0');
    }

    for(int i = 1; i <= 8; i ++) start += char('0' + i);

    int step = bfs(start,end);
    cout << step << endl;

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

    reverse(res.begin(),res.end());

    if(step > 0) cout << res << endl;

    return 0;
}

代码详解

数组解释

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

char g[2][4];//相当于一个temp 暂存一个魔板的二维状态

unordered_map<string, pair<char, string>> pre;

是一个pre的映射数组//有点像单链表
存一个pre的map里面是一个string和一个pair
将string 映射到 pair里面
也就是说用一个pair来记录string的信息
pair里面有两条信息
second 是 一串string 代表他由哪个string转化而来
first 是一个 char 代表 他的前继是通过何种操作转化而来

unordered_map<string, int> dist;
将当前串string 映射 到他的步数里面
或曰 用一个int 来记录 到达string 的dist；

主函数解释

cin >> x;
end +=char(x + '0');

单字符读入，字符串填加，妙极

    while(end != start)
    {
        res += pre[end].first;
        end = pre[end].second;
    }
    像单链表一样遍历

  数组是特殊的map，存的是下标和内容的映射关系
  如
  int a[100]; 
  相当于
  map<int, int>a;

  这样定义下
  a[1] = 5;

  这种使用是等价的；下面图片是更一般的map

bfs()解释

queue<string> q;
    q.push(start);
    dist[start] = 0;

把队头放进队列中
距离更新为0

auto t = q.front();
        q.pop();

        string m[3];
        m[0] = move0(t);
        m[1] = move1(t);
        m[2] = move2(t);

只要队列不空，我们就把队头拿出来；
开一个string 组 存一下由队头扩张出来的三种情况

for(int i = 0; i < 3 ; i++)
          if(!dist.count(m[i]))//unused ???
          {
              dist[m[i]] = dist[t] + 1;
              pre[m[i]] = {'A' + i, t};
              q.push(m[i]);
              if(m[i] == end) return dist[end];
          }

遍历一遍三种情况
if（）表示只要没有扩展到过，我们就把当前string的距离更新为他前继的距离加一
然后发个身份证，记录一下他的来源（表示他的爸爸是前继string 经过char操作而来）
然后把他加到队列里面等待遍历

if(m[i] == end) return dist[end]; 表示如果找到了就返回
由于第一个if的条件保障了每个点都是第一次找到，所以第一次找到，我们就反回。
在main里面根据pre 找回；

函数

简单的几个函数写写啦