46届ICPC沈阳站铜牌题Luggage Lock（BFS）

写在前面

这个题是去年打沈阳站我队没有做出来的题目，我觉得算铜牌题吧，当时要是做出来了我们就是铜牌了，差一点做到一赛季都是铜没有铁的“壮举”哈哈。
周日（4.24）的训练我还是避开了这个题，做别的题去了，可能是内心的恐惧吧，现在来赛后补题

题意

题目链接：J-Luggage Lock_第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（沈阳） (nowcoder.com)
给你两个由'0'...'9'组成的长度为$4$的字符串$s1$,$s2$，每次可以选择连续的部分进行$+1$或者$-1$，其实就是类似于我们的密码锁，如图：

求从$s1$到$s2$至少需要多少次

思路

思路就是预处理出所有情况，用BFS，然后之后的t组询问，每次直接输出即可，至于怎么BFS，来看下面：

首先我列出了所有情况，

string s[]={//10种情况  又有加减 所以是20种
    "1000","0100","0010","0001",
    "1100","0110","0011",
    "1110","0111","1111"
    };

我们用1来表示移动一次（具体是加还是减看另外一个参数），0表示不动，从上面可以看出，每一次操作确实是连续的，这个题我觉得用字符串比较好，越界什么的看后面的

然后有一个规范化的操作，很简单就是if判断有没有出界

inline void norm(string &x)
{
    for (auto &c : x)
    {
        if (c>'9') c=char(c-10);
        if (c<'0') c=char(c+10);
    }
}

因为计算的时候，有加分和减法区别，可以写两个if判断一下，我写完之后发现可以合并，那还是合并吧哈哈

inline string calc(string a,string b,int t)
{
    string res="";
    for (int i=0;i<a.size();i++)
        res=res+char(a[i]+(b[i]-'0')*t);//t=1 or t=-1
    norm(res);//规范化
    return res;
}

然后就是BFS部分，就很简单了，从"0000"开始即可，也许会问给出的$s1$并不是"0000"，为什么这样呢？实际上拿$s2-s1$“得出来”的“差”就是从"0000"到新的$str$的差距，比如"1111"到"2345"和"0000"到"1234"是没有区别的

因为是string，我直接定义map<string,int> ans;

inline void init()
{
    queue<string> q;
    q.push("0000");
    ans["0000"]=0;
    while (!q.empty())
    {
        string cur = q.front();
        q.pop();
        for (int i=0;i<10;i++)
        {
            string next = calc(cur,s[i],1);//计算下一个，这里是加法
            if (ans.find(next)==ans.end())//没有出现过
            {
                ans[next]=ans[cur]+1;
                q.push(next);
            }
            next = calc(cur,s[i],-1);//计算下一个，这里是减法
            if (ans.find(next)==ans.end())//没有出现过
            {
                ans[next]=ans[cur]+1;
                q.push(next);
            }
        }
    }
}

这样就大功告成了，接下来读入的话就按照思路先做差，然后直接输出答案就可以了。

inline void Case_Test()
{
    cin>>s1>>s2;
    string res="";
    for (int i=0;i<4;i++)
        res=res+char(s2[i]-s1[i]+'0');
    norm(res);
    cout<<ans[res]<<endl;
}

代码

string s1,s2;
map<string,int> ans;
string s[]={
    "1000","0100","0010","0001",
    "1100","0110","0011",
    "1110","0111","1111"
    };

inline void norm(string &x)
{
    for (auto &c : x)
    {
        if (c>'9') c=char(c-10);
        if (c<'0') c=char(c+10);
    }
}

inline string calc(string a,string b,int t)
{
    string res="";
    for (int i=0;i<a.size();i++)
        res=res+char(a[i]+(b[i]-'0')*t);
    norm(res);
    return res;
}

inline void init()
{
    queue<string> q;
    q.push("0000");
    ans["0000"]=0;
    while (!q.empty())
    {
        string cur = q.front();
        q.pop();
        for (int i=0;i<10;i++)
        {
            string next = calc(cur,s[i],1);
            if (ans.find(next)==ans.end())
            {
                ans[next]=ans[cur]+1;
                q.push(next);
            }
            next = calc(cur,s[i],-1);
            if (ans.find(next)==ans.end())
            {
                ans[next]=ans[cur]+1;
                q.push(next);
            }
        }
    }
}

inline void Case_Test()
{
    cin>>s1>>s2;
    string res="";
    for (int i=0;i<4;i++)
        res=res+char(s2[i]-s1[i]+'0');
    norm(res);
    cout<<ans[res]<<endl;
}