HDU1195 ZOJ2416 Open the Lock【BFS】

Open the Lock

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6675 Accepted Submission(s): 3014

Problem Description

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 will 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.

Input

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.

Output

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

Sample Input

Sample Output

2
4

Author

YE, Kai

Source

Zhejiang University Local Contest 2005

问题链接：HDU1195 ZOJ2416 Open the Lock。

题意简述：输入测试用例数t，每个例子包括两个４个数字的整数（由１到９组成），一个为源，另外一个为目标。每次可以将其中任何一个数字+1或者-1运算，并且规定1-1＝9，9+1=1；也可以将相邻２位数进行交换。问最少需要变换几次，才能从源变为目标。

问题分析：该问题可以用BFS来解决。在BFS搜索过程中，出现过的４位数就不必再试探了，因为再用这个４位数变下去其次数不可能比上次开始的变换次数少。

程序说明：

每个节点既保存４位整数值，也分别保存４位数字于数组中，有利于变换也有利于比较。编写了函数myatoi()用于将数字的值串（不是数字字符的串）转换为整数。数组notvist[]用于避免重复搜索。

本程序虽然略长，但是程序逻辑清晰易懂。

AC的C++语言程序如下：

/* HDU1195 ZOJ2416 Open the Lock */

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int MAXN = 4;

struct node {
    char num[MAXN+1];
    int a;
    int level;
};

node start;
int b;

bool notvist[10000];

int myatoi(char *s)
{
    int result = 0;

    while(*s) {
        result *= 10;
        result += *s;
        s++;
    }

    return result;
}

int bfs()
{
    int i, temp = start.a;
    for(i=0; i<MAXN; i++) {
        start.num[MAXN - 1 - i] = temp % 10;
        temp /= 10;
    }
    start.num[i] = '';
    start.level = 0;

    notvist[start.a] = false;

    memset(notvist, true, sizeof(notvist));

    queue<node> q;
    q.push(start);

    while(!q.empty()) {
        node front = q.front();
        q.pop();

        if(myatoi(front.num) == b)
            return front.level;

        node v;

        // exchange
        for(i=1; i<=MAXN-1; i++) {
            strcpy(v.num, front.num);

            int t = v.num[i-1];
            v.num[i-1] = v.num[i];
            v.num[i] = t;

            v.a = myatoi(v.num);
            if(notvist[v.a]) {
                v.level = front.level + 1;
                q.push(v);

                notvist[v.a] = false;
            }
        }

        // plus 1
        for(i=0; i<MAXN; i++) {
            strcpy(v.num, front.num);

            v.num[i]++;
            if(v.num[i] == 10)
                v.num[i] = 1;

            v.a = myatoi(v.num);
            if(notvist[v.a]) {
                v.level = front.level + 1;
                q.push(v);

                notvist[v.a] = false;
            }
        }

        // minus 1
        for(i=0; i<MAXN; i++) {
            strcpy(v.num, front.num);

            v.num[i]--;
            if(v.num[i] == 0)
                v.num[i] = 9;

            v.a = myatoi(v.num);
            if(notvist[v.a]) {
                v.level = front.level + 1;
                q.push(v);

                notvist[v.a] = false;
            }
        }
    }

    return 0;
}

int main()
{
    int t, ans;

    cin >> t;
    while(t--) {
        cin >> start.a >> b;

        ans = bfs();

        cout << ans << endl;
    }

    return 0;
}