BFS：Open and Lock(一个数的逐位变化问题的搜索)

解体心得：

1、关于定义四维数组的问题，在起初使用时，总是在运行时出错，找了很多方法，最后全部将BFS（）部分函数写在主函数中，将四维数组定义在主函数中才解决了问题。运行成功后再次将四维数组定义为全局变量，BFS（）函数独立出来没发生运行错误。很纠结，找了三天的BUG！

2、关于一个数的逐位变换，BFS（）中有三个主要变换+1循环，-1循环，邻位交换循环。思路清晰，简单。

3、注意step+1的位置与Next = now 的位置的关系！

题目：

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

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

2

1234

2144

1111

9999

Sample Output

2

4

#include<stdio.h>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

char now1[4],Next1[4];

int use[10][10][10][10];

struct num1

{

    int a[4];

    int step;

}now,Next,aim;

void BFS()

{

    queue <num1> qu;

    qu.push(now);

    use[now.a[0]][now.a[1]][now.a[2]][now.a[3]] = 1;

    while(!qu.empty())

    {

        now = qu.front();

        qu.pop();

        //交换部分

        for(int i=0;i<3;i++)

        {

            Next = now;

            Next.step = now.step + 1;

            Next.step = now .step + 1;

            swap(Next.a[i],Next.a[i+1]);

            if(Next.a[0] == aim.a[0] && Next.a[1] == aim.a[1] && Next.a[2] == aim.a[2] && Next.a[3] == aim.a[3])

            {

                printf("%d\n",Next.step);

                return;

            }

            if(!use[Next.a[0]][Next.a[1]][Next.a[2]][Next.a[3]])

            {

                qu.push(Next);

                use[Next.a[0]][Next.a[1]][Next.a[2]][Next.a[3]] = 1;

            }

        }

        //+1部分

        for(int i=0;i<4;i++)

        {

            Next = now;

            Next.step = now.step + 1;

            Next.a[i] = now.a[i] + 1;

            if(Next.a[i] == 0)

                Next.a[i] = 9;

            if(Next.a[i] == 10)

                Next.a[i] = 1;

            if(Next.a[0] == aim.a[0] && Next.a[1] == aim.a[1] && Next.a[2] == aim.a[2] && Next.a[3] == aim.a[3])

            {

                printf("%d\n",Next.step);

                return;

            }

            if(!use[Next.a[0]][Next.a[1]][Next.a[2]][Next.a[3]])

            {

                qu.push(Next);

                use[Next.a[0]][Next.a[1]][Next.a[2]][Next.a[3]] = 1;

            }

        }

        //-1部分

        for(int i=0;i<4;i++)

        {

            Next = now;

            Next.step = now.step + 1;

            Next.a[i] = now.a[i] - 1;

            if(Next.a[i] == 0)

                Next.a[i] = 9;

            if(Next.a[i] == 10)

                Next.a[i] = 1;

            if(Next.a[0] == aim.a[0] && Next.a[1] == aim.a[1] && Next.a[2] == aim.a[2] && Next.a[3] == aim.a[3])

            {

                printf("%d\n",Next.step);

                return;

            }

            if(!use[Next.a[0]][Next.a[1]][Next.a[2]][Next.a[3]])

            {

                qu.push(Next);

                use[Next.a[0]][Next.a[1]][Next.a[2]][Next.a[3]] = 1;

            }

        }

    }

}

int main()

{

    int t;

    int sum_step;

    scanf("%d",&t);

    while(t--)

    {

        memset(use,0,sizeof(use));

        scanf("%s",now1);

        getchar();

        scanf("%s",Next1);

        for(int i=0;i<4;i++)

            now.a[i] = now1[i] - '0';

        for(int i=0;i<4;i++)

            aim.a[i] = Next1[i] - '0';

        now.step = 0;

        BFS();

    }

}

巴特西

BFS：Open and Lock(一个数的逐位变化问题的搜索)

最新文章

热门文章