首页 > ACM题库 > HDU-杭电 > HDU 1195 Open the Lock-BFS-[解题报告] C++
2013
12-04

HDU 1195 Open the Lock-BFS-[解题报告] C++

Open the Lock

问题描述 :

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.

输入:

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.

样例输入:

2
1234
2144

1111
9999

样例输出:

2
4

 题意:有一个四位数字的字符串,要求将初始数字串改变成目标数字串,允许的操作有两种:

1、将每一位加1或减1操作,1减1操作变成9,9加1操作变成1;

2、交换相邻的两个字符;

每一种操作为一步,求最少要用多少步才能完成从初始状态到目标状态。

注意:首个字符和最后一个字符不算相邻。

思路:将上面两步分解成四个步骤操作,加1,减1,向左交换,向右交换。用bfs搜索每一种操作状态,找到目标状态就把这次找到目标状态所花的步骤和已经有的最少步骤作比较,这次所用步骤少就将值赋给最少步骤。

最小步骤用steps 保存。

数据结构

struct  Q

{

int x [4];// 每一位的数字

int steps;//当前状态已经花费的时间

}

bool vis[10000];//存储已经访问过的每一种状态,如果已经访问过此种状态就不在访问了。

代码:

#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
int s1,s2,s3,s4;
int e1,e2,e3,e4;
int steps;
bool vis[10000];
struct Q
{
    int x[4];
    int steps;
};
void bfs()
{
    queue<Q>q;
    Q temp,now;
    int i,j;
    int x[4];
    int bit[4]={1000,100,10,1};

    while(!q.empty())q.pop();
    temp.x[0]=s1; temp.x[1]=s2;
    temp.x[2]=s3; temp.x[3]=s4;
    temp.steps=0;
    q.push(temp);
    steps=0xfffffff;
    memset(vis,0,sizeof(vis));
    vis[s1*1000+s2*100+s3*10+s4]=1;
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        if(now.x[0]==e1&&now.x[1]==e2&&now.x[2]==e3&&now.x[3]==e4)
        {

            if(steps>now.steps)
            {
                steps=now.steps;
            }
        }
        for(i=0;i<4;i++)
        {
            for(j=0;j<4;j++)
            {
                x[0]=now.x[0];x[1]=now.x[1];
                x[2]=now.x[2];x[3]=now.x[3];
                temp=now;
                if(j==0)
                {
                    x[i]++;
                    if(x[i]>9)x[i]=1;
                }
                else
                if(j==1)
                {
                    x[i]--;
                    if(x[i]<1)x[i]=9;
                }
                else
                if(j==2)
                {
                    if(i<=0)continue;
                    int t=x[i];
                    x[i]=x[i-1];
                    x[i-1]=t;
                }
                else
                {
                    if(i>=3)continue;
                    int t=x[i];
                    x[i]=x[i+1];
                    x[i+1]=t;
                }
                //printf("%d %d %d %d\n",x[0],x[1],x[2],x[3]);
                if(vis[x[0]*bit[0]+x[1]*bit[1]+x[2]*bit[2]+x[3]*bit[3]])continue;
                vis[x[0]*bit[0]+x[1]*bit[1]+x[2]*bit[2]+x[3]*bit[3]]=1;
                temp.x[0]=x[0];temp.x[1]=x[1];temp.x[2]=x[2];temp.x[3]=x[3];

                temp.steps++;
                q.push(temp);
            }
        }
    }
    return;
}

int main()
{
    int t;
    char str[5];

    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",str);
        s1=str[0]-'0'; s2=str[1]-'0';
        s3=str[2]-'0'; s4=str[3]-'0';
        scanf("%s",str);
        e1=str[0]-'0'; e2=str[1]-'0';
        e3=str[2]-'0'; e4=str[3]-'0';
        bfs();
        printf("%d\n",steps);
    }
    return 0;
}