Luggage Lock_综合

原题链接

题意

给一个锁，每次可以选择连续的一段拨动一次，给定一个初始状态，再给定一个目标状态，问从初始状态转到目标状态需要几步？

思路

问最短几步首先想到 $B F S$ 可以求最短路的特性。

然后我们看从初始状态到目标状态，需要怎么转，就用 $a [i] ? b [i]$ ，得到给定初始到目标的转法，然后我们可以把它转换成从0000到目标状态，也就是说把负数 $+ 10$ ，其实一起（含正数） $+ 10$ 也可以， $%10\%10$ 就可以了。

现在问题就变成了从0000到一个目标状态（就是上面所说的转法）需要几步。

用 $B F S + m a p$ 打表即可。

代码

#include<bits/stdc++.h>
using namespace std;int start[4] = {
    0, 0, 0, 0};
int End[4] = {
    9, 9, 9, 9}; struct node
{
    int f[4];
};string change(int a[])
{
    string s = "";for (int i = 0; i < 4; i ++ ){
    s.push_back(a[i] + '0');}return s;
}unordered_map<string, int> ans;
int caozuo[20][4] ={
    {
    1, 0, 0, 0}, {
    1, 1, 0, 0}, {
    1, 1, 1, 0}, {
    1, 1, 1, 1}, {
    0, 1, 0, 0},  {
    0, 1, 1, 0}, {
    0, 1, 1, 1}, {
    0, 0, 1, 0}, {
    0, 0, 1, 1}, {
    0, 0, 0, 1}, {
    -1, 0, 0, 0}, {
    -1, -1, 0, 0}, {
    -1, -1, -1, 0}, {
    -1, -1, -1, -1}, {
    0, -1, 0, 0},  {
    0, -1, -1, 0}, {
    0, -1, -1, -1}, {
    0, 0, -1, 0}, {
    0, 0, -1, -1}, {
    0, 0, 0, -1}};void bfs()
{
    queue<node> q;node head;memcpy(head.f, start, sizeof start);q.push(head);while (!q.empty()){
    node t = q.front();
// cout << change(t.f) << endl;int d = ans[change(t.f)];q.pop();for (int i = 0; i < 20; i ++ ){
    node newnode;memcpy(newnode.f, t.f, sizeof t.f);for (int j = 0; j < 4; j ++ ){
    newnode.f[j] += caozuo[i][j];//注意处理负数的情况newnode.f[j] = newnode.f[j] + 10 ;newnode.f[j] %= 10;}bool flag = 0;for (int j = 0; j < 4; j ++ ){
    if (newnode.f[j] > 9 || newnode.f[j] < 0) {
    flag = 1;break;}}if (flag) continue;string tt = change(newnode.f);if (!ans.count(tt)){
    ans[tt] = d + 1;q.push(newnode);}}}
}int main()
{
    int t; cin >> t;bfs();while (t -- ){
    string a, b;cin >> a >> b;for (int i = 0; i < 4; i ++ ){
    End[i] = ((a[i] - '0') - (b[i] - '0') + 10) % 10;}
// cout << change(End) << endl;cout << ans[change(End)] << endl;}return 0;
}

总结

人都傻了，我还搁那双向广搜呢。。。
附上代码


//f 搜索
#include<bits/stdc++.h>
#define endl '\n' 
// #define int long long
using namespace std;
const int N = 2e5+10;
typedef long long ll;int start[4];
int End[4];struct node{
    int f[4];
};string change(int a[])
{
    string s = "";for (int i = 0; i < 4; i ++ ){
    s.push_back(a[i] + '0');}return s;
}
int caozuo[20][4] ={
    {
    1, 0, 0, 0}, {
    1, 1, 0, 0}, {
    1, 1, 1, 0}, {
    1, 1, 1, 1}, {
    0, 1, 0, 0},  {
    0, 1, 1, 0}, {
    0, 1, 1, 1}, {
    0, 0, 1, 0}, {
    0, 0, 1, 1}, {
    0, 0, 0, 1}, {
    -1, 0, 0, 0}, {
    -1, -1, 0, 0}, {
    -1, -1, -1, 0}, {
    -1, -1, -1, -1}, {
    0, -1, 0, 0},  {
    0, -1, -1, 0}, {
    0, -1, -1, -1}, {
    0, 0, -1, 0}, {
    0, 0, -1, -1}, {
    0, 0, 0, -1}};int kuozhan(queue<node>& q, unordered_map<string, int>& ma, unordered_map<string, int>& mb)
{
    int d = ma[change(q.front().f)];while (!q.empty() && ma[change(q.front().f)] == d){
    node t;t = q.front();q.pop();for (int i = 0; i < 20; i ++ ){
    node newnode;memcpy(newnode.f, t.f, sizeof t.f);for (int j = 0; j < 4; j ++ ){
    newnode.f[j] += caozuo[i][j];}string z = change(newnode.f);if (mb.count(z)) return d + 1 + mb[z];if (ma.count(z)) continue;ma[z] = d + 1;q.push(newnode);}}return -1;
}int bfs()
{
    queue<node> qa, qb;unordered_map<string, int> ma, mb;node head;memcpy(head.f, start, sizeof start);ma[change(head.f)] = 0;qa.push(head);memcpy(head.f, End, sizeof End);mb[change(head.f)] = 0;qb.push(head);while (!qa.empty() && !qb.empty()){
    int temp = -1;if (qa.size() >= qb.size()){
    temp = kuozhan(qa, ma, mb);}else{
    temp = kuozhan(qb, mb, ma);}if (temp != -1){
    return temp;}}return -1;
}signed main()
{
    // ios::sync_with_stdio(false);// cin.tie(0),cout.tie(0);int t;cin>>t;while(t--){
    for (int i = 0; i < 4; i ++ ){
    scanf("%1d", &start[i]);// cin >> start[i];}for (int i = 0; i < 4; i ++ ){
    scanf("%1d", &End[i]);// cin >> End[i];}cout << bfs() << endl;}return 0;
}