题目
思路
我们可以将密码锁的每一个状态看成一个节点,每一个操作看成从一个节点到另一个节点的权重为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;
}
标签:qs,Luggage,int,Lock,ts,++,ms,沈阳站,nes
From: https://www.cnblogs.com/Leoyby/p/16804224.html