HDU - 1195 Open the Lock

传送门：HDU - 1195

题目描述

Now an emergent task for you is to open a password lock. The password is consisted of four digits. Each digit is numbered from 1 to 9.
Each time, you can add or minus 1 to any digit. When add 1 to ‘9’, the digit will change to be ‘1’ and when minus 1 to ‘1’, the digit wil change to be ‘9’. You can also exchange the digit with its neighbor. Each action will take one step.

Now your task is to use minimal steps to open the lock.

Note: The leftmost digit is not the neighbor of the rightmost digit.

输入描述

The input file begins with an integer T, indicating the number of test cases.

Each test case begins with a four digit N, indicating the initial state of the password lock. Then followed a line with anotther four dight M, indicating the password which can open the lock. There is one blank line after each test case.

输出描述

For each test case, print the minimal steps in one line.

思路分析

将一个数通过一系列操作变成另一个数，对于每一位可以有四种操作，+1，-1，或者交换相邻，直接bfs。

样例输入

2
1234
2144

1111
9999

样例输出

2
4

AC代码

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
#include <unordered_map>

using namespace std;

#define fi first
#define se second
#define ll long long
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

const int INF = 0x3f3f3f3f;

inline int read () {
    register int s = 0, w = 1;
    register char ch = getchar ();
    while (! isdigit (ch)) {if (ch == '-') w = -1; ch = getchar ();}
    while (isdigit (ch)) {s = (s << 3) + (s << 1) + (ch ^ 48); ch = getchar ();}
    return s * w;
}

string s,x;
int len,ans;

struct node{
    string s;
    int d;
};

unordered_map<string,int> ma;
int cnt=0;

void bfs(){
    queue<node>q;
    node a;
    a.s=x;
    a.d=0;
    q.push(a);
    while(!q.empty()){
        node next;
        node now=q.front();
        q.pop();
        if(now.s==s){
            ans=now.d;
            break;
        }
        for(int i=0;i<len;i++){
            string x;
            x=now.s;
            if(s[i]==x[i])
                continue;
            if(x[i]=='9'){
                x[i]='1';
                next.s=x;
                next.d=now.d+1;
                if(!ma[x]){
                    ma[x]++;
                    q.push(next);
                }
                x[i]='8';
                next.s=x;
                next.d=now.d+1;
                if(!ma[x]){
                    ma[x]++;
                    q.push(next);
                }
                
                
            }else
            if(x[i]=='1'){
                x[i]='9';
                next.s=x;
                next.d=now.d+1;
                if(!ma[x]){
                    ma[x]++;
                    q.push(next);
                }
                
                x[i]='2';
                next.s=x;
                next.d=now.d+1;
                if(!ma[x]){
                    ma[x]++;
                    q.push(next);
                }
                
                
            }else{
                x=now.s;
                x[i]++;
                next.s=x;
                next.d=now.d+1;
                if(!ma[x]){
                    ma[x]++;
                    q.push(next);
                }
                
                x=now.s;
                x[i]--;
                next.s=x;
                next.d=now.d+1;
                if(!ma[x]){
                    ma[x]++;
                    q.push(next);
                }
                
                
            }
            if(i!=len-1){
                x=now.s;
                swap(x[i],x[i+1]);
                next.s=x;
                next.d=now.d+1;
                if(!ma[x]){
                    ma[x]++;
                    q.push(next);
                }
                
                
            }
            if(i!=0){
                x=now.s;
                swap(x[i],x[i-1]);
                next.s=x;
                next.d=now.d+1;
                if(!ma[x]){
                    ma[x]++;
                    q.push(next);
                }
            }

        }
    }
    return ;
}

int main() {
    
    int t;
    t=read();
    while(t--){
        ans=0;
        ma.clear();
        cin>>s>>x;
        ma[x]++;
        len=s.size();
        bfs();
        printf("%d\n",ans);
    }
    return 0;
}