2021ICPC沈阳站 J Luggage Lock 思路以及C++实现

题目

J Luggage Lock

思路

我们可以将密码锁的每一个状态看成一个节点，每一个操作看成从一个节点到另一个节点的权重为1（意思是经过一次操作）的有向边，这个问题就可以看成一个最短路问题。
由于所有边的权重一致，我们可以使用bfs得出最短距离。
但问题是题目有T个测试集，有T个源点，可能互不相同，如果对每一个源点进行bfs会超时，需要将源点经行统一。
我们可以算出s到t的每一位上的“相对距离”，这样可以将源点统一成“0000”，就只需要一遍bfs。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
using namespace std;
using PSS = pair<string, string>;
// 由题可知，对密码锁有20个操作，相当于一个节点可以有20个条边
const int BIAS[20][4] = 
{{1,0,0,0},{0,1,0,0},{0,0,1,0},{0,0,0,1},
{-1,0,0,0},{0,-1,0,0},{0,0,-1,0},{0,0,0,-1},
{1,1,0,0},{-1,-1,0,0},{0,-1,-1,0},{0,1,1,0},
{0,0,1,1},{0,0,-1,-1},{1,1,1,0},{-1,-1,-1,0},
{0,1,1,1},{0,-1,-1,-1},{1,1,1,1},{-1,-1,-1,-1}};

unordered_map<string, int64_t> luggage(const string &s, const unordered_set<string> &ts);

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    vector<string> ts(T);
    for(int i = 0;i < T; ++i)
    {
        string a, b, c = "0000";
        cin >> a >> b;
        for(int j = 0;j < 4; ++j)
        {
        	// 计算每一位上的“相对位移”
          	// 这样就将a->b的最短距离转化为"0000"->c的最短距离
            c[j] = (a[j] - b[j] + 10) % 10 + '0';
        }
        ts[i] = c;
    }

    auto dict = luggage("0000", unordered_set<string>(ts.begin(), ts.end()));
    for(int i = 0;i < T; ++i)
    {
        cout << dict[ts[i]] << '\n';
    }
    return 0;
}

// bfs
// s表示源点，ts是终点的集合
unordered_map<string, int64_t> luggage(const string &s, const unordered_set<string> &ts)
{
    queue<string> qs;
    unordered_map<string, int64_t> ms, dict;
    qs.emplace(s);
    ms[s] = 0;

    while (!qs.empty())
    {
        string t = qs.front();
        qs.pop();
        int64_t d = ms[t];
        
        int cur[4];
        for(int i = 0;i < 4; ++i)
            cur[i] = t[i] - '0';

        for(int i = 0;i < 20; ++i)
        {
            

            int ne[4];
            for(int j = 0;j < 4; ++j)
            {
                ne[j] = (cur[j] + BIAS[i][j] + 10) % 10;
            }
            string nes = "0000";
            for(int j = 0;j < 4; ++j)
                nes[j] = (char)(ne[j] + '0');
            
            if(ms.find(nes) != ms.end())
                continue;
            
            ms[nes] = d + 1;
            qs.emplace(nes);

            if(ts.find(nes) != ts.end())
            {
                dict[nes] = ms[nes];

                // 当所有点的距离都求出来后，就可以返回结果了
                if(dict.size() == ts.size())
                    goto BK2;
            }
        }
    }
    BK2:
    return dict;
}