2021 ICPC沈阳 J.Luggage Lock（bfs，模拟）

题目描述

题目链接

题目分析

$这是一道很明显的bfs+模拟的题（和八数码是一类题）$

$因为起点和终点都不一样，还有1e5个测试样例。因此不能直接对每一组样例都做一遍bfs，肯定会超时。$

$因此我们可以将所有测试样例的起点都转化为0000，终点对应变为t[i]-s[i]（s为起点，t为终点）$

$这样转换之后，我们可以以0000作为起点进行一遍bfs，同时记录下到达每个状态所需的步数。这样对于$$每个测试样例即可O(1)输出答案。$

代码如下

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
#include <iomanip>
#define LL long long
#define ULL unsigned long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define PDD pair<double,double>
#define x first
#define y second
using namespace std;
const int N=1e5+5,mod=1e9+7;
map<string,int> f;
//用map记录到达每个状态的步数
void bfs()
{
queue<string> q;
q.push("0000");
//“0000”为起点
f["0000"]=0;
while(q.size())
{
auto u=q.front();
q.pop();
string a,b;
for(int i=0;i<4;i++)
//枚举每一个区间[i,j]
for(int j=i;j<4;j++)
{
a=b=u;
for(int k=i;k<=j;k++)
{
a[k]=(u[k]-'0'+1)%10+'0';
//a记录u在[i,j]区间内+1得到的状态
b[k]=(u[k]-'0'+9)%10+'0';
//b记录u在[i,j]区间内-1得到的状态
}
if(f.find(a)==f.end())
//如果f中没有a状态，则将其放入队列
{
q.push(a);
f[a]=f[u]+1;
}
if(f.find(b)==f.end())
//同上
{
q.push(b);
f[b]=f[u]+1;
}
}
}
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
bfs();
//bfs预处理出所有答案
int T;
cin>>T;
while(T--)
{
string s,t;
cin>>s>>t;
//将起点转化为0000，终点变为t[i]-s[i]
for(int i=0;i<4;i++) t[i]=(t[i]-s[i]+10)%10+'0';
cout<<f[t]<<endl;
//输出答案
}
return 0;
}

最后

以上就是留胡子羽毛为你收集整理的2021 ICPC沈阳 J.Luggage Lock（bfs，模拟）的全部内容，希望文章能够帮你解决2021 ICPC沈阳 J.Luggage Lock（bfs，模拟）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。