cf 103427 Luggage Lock | vegeone

vegeone
0%

cf 103427 Luggage Lock

发表于 分类于 Valine：

题意

给定n位字符串，可以对连续的几位都进进行+1/-1的操作，求变成目标串最少的操作次数

思路

这里涉及到一个概念叫做相对距离，对于从起始串到目标串的变化可以转化为0000串到某个串的变化，每一位的相对距离保持不变即可。

这样我们就只需要预处理求出0000串到所有状态的最小操作次数即可，可以通过BFS来求出并记录。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
// #define int long long
using namespace std;
#define endl '\n'
const int N=1e5+10;
typedef pair<string,int>pp;
map<string,int>mp;
void solve()
{
    string s,t;
    cin>>s>>t;
    // cerr<<s<<" "<<t<<" "<<mp[s]<<" "<<mp[t]<<endl;
    string ans="";
    for(int i=0;i<4;++i){
        if(s[i]<t[i]){
            ans+=s[i]+10-t[i]+'0';
        }else {
            ans+=s[i]-t[i]+'0';
        }
    }
    cout<<mp[ans]<<endl;
}
queue<pp>q;
void bfs(string ss){
    q.push({ss,0});
    mp[ss]=0;
    while(q.size()){
        auto temp=q.front();
        q.pop();

        string val=temp.first;
        int num=temp.second;
        // if(mp[val])continue;
        // cerr<<val<<endl;

        for(int i=0;i<2;++i){
            for(int j=0;j<4;++j){
                auto tt=val;
                for(int k=j;k<4;++k){
                    if(i==0){
                        tt[k]=tt[k]=='0'?'9':tt[k]-1;
                    }else {
                        tt[k]=tt[k]=='9'?'0':tt[k]+1;
                    }
                    // cerr<<tt<<endl; 
                    if(!mp[tt]&&tt!="0000"){
                        q.push({tt,num+1});
                        mp[tt]=num+1;
                    }
                }
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    bfs("0000");
    int T;
    cin>>T;
    while(T--)	solve();
    return 0;
}