算法提高课汇总

算法思路

最小步数模型: 将整个“图”视为一个状态也即一个节点. 状态的转移视为权值为1的边.

$BFS$求解, 注意几点:

• 状态的存储: 一般用字符串存储状态, 用哈希表存储初始状态到每个状态的距离.

• 方案记录: 记忆数组存储. 本题中需要存储上一个状态以及对应操作.

• 字典序: 每次状态转移都按$A\sim C$的顺序, 得到的方案一定是字典序最小的方案.

  一种直观理解: 这种扩展方式恰好是字典序定义的顺序.
  也可用反证法证明: 假设用上述方式得到的方案不是字典序最小.
  每个方案对应一个字符串, 从左向右依次考虑每个字母(操作).
  考虑算法解与最优解从左向右第一个不同字母: $x$与$x’$, 假设在第$k$个位置不同.
  由于最优解字典序更小, 有$x’\lt x$. $x$与$x’$都是可以到达题目要求状态的合法操作.
  而在第$k$步扩展时, 算法是按照$A\sim C$顺序选取, 即算法解一定是取队列中最前面的合法操作.
  最优解与算法解不同, 而算法解保证取队列最前面的合法操作, 且队列具有单调性, 所以: $x\le x’$.
  (队列前的操作字典序小于队列后面操作的字典序, 这是算法操作的结果).
  与假设矛盾. 后续的不同字母依次类推, 所以上述方法得到的算法解一定是字典序最小的方案.

代码实现

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

using namespace std;

char g[2][4];
queue<string> que;
unordered_map<string, int> d;
unordered_map<string, pair<char, string>> pre;

void set(string &state) //一维 -> 二维 方便操作
{
    int k = 0;
    for( int i = 0; i < 4; i ++ )   g[0][i] = state[k ++];
    for( int i = 3; i >= 0; i -- )  g[1][i] = state[k ++];
}

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);

    char c0 = g[0][3], c1 = 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] = c0, g[1][0] = c1;

    return get();
}

string move2(string state)
{
    set(state);

    char c = g[0][1];
    g[0][1] = g[1][1];
    g[1][1] = g[1][2];
    g[1][2] = g[0][2];
    g[0][2] = c;

    return get();
}

void bfs(string start, string end)
{
    d[start] = 0;
    que.push(start);

    while( que.size() )
    {
        string state = que.front(); que.pop();

        if( state == end )  break;

        string state_[3];
        state_[0] = move0(state); //状态转移
        state_[1] = move1(state);
        state_[2] = move2(state);

        for( int i = 0; i < 3; i ++ )
        {
            string temp = state_[i];
            if( !d[temp] )
            {
                d[temp] = d[state] + 1;
                pre[temp] = {char(i + 'A'), state}; //记录上一步操作, 状态
                que.push(temp);
            }
        }
    }
}

int main()
{
    string start, end;
    for( int i = 1; i <= 8; i ++ )
    {
        int t;
        cin >> t;
        end += char(t + '0');
    }

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

    bfs(start, end);

    cout << d[end] << endl;
    string res;
    while( end != start )
    {
        res += pre[end].first;
        end = pre[end].second;
    }
    reverse(res.begin(), res.end());
    if( res.size() )    cout << res << endl;

    return 0;
}