pku1184 聪明的打字员

#include<stdio.h>
#include<math.h>
#include<queue>
#include<algorithm>
using namespace std;

//0:0                        //最终发生操作的访问位置只有这十种样式

//1:0, 1

//2:0, 1, 2

//3:0, 1, 2, 3

//4:0, 1, 2, 3, 4        

//5:0, 5

//6:0, 1, 5

//7:0, 1, 2, 5

//8:0, 1, 2, 3, 5

//9:0, 1, 2, 3, 4, 5


bool visit[1000000][10]; //记录某个密码在哪种操作位置被访问,由于存在left、right操作使密码值不变，必需增加一维记录操作位置

struct Node
{
    int number,step,kind;        //number表示从源密码转换成目标密码中的中间密码，step表示从原始密码转换到中间密码所经过的步数，kind表示中间密码number的访问种类

    Node(){}
    Node(int _number,int _step,int _kind):number(_number),step(_step),kind(_kind){}
};
int match[6];

void toArray(int temp,int s[])
{;
    for(int i=5;i>=0;i--)
    {
        s[i]=temp%10;
        temp/=10;
    }
}

int switchDigit(int pos1,int pos2,int temp)    
{
    int s[6];
    toArray(temp,s);
    swap(s[pos1],s[pos2]);
    int ans=0;
    for(int i=0;i<6;i++)
    {
        ans=ans*10+s[i];
    }
    swap(s[pos1],s[pos2]);
    return ans;
}

int check(Node &temp)    //中间密码的操作种类中的未访问位与目标密码不同则return不匹配，否则return比较中间密码的各个位通过up、down实现目标密码所需的步数

{
    int ans=0,s[6];
    toArray(temp.number,s);
    if(temp.kind<=4)    
    {
        for(int i=temp.kind+1;i<6;i++)
        {
            if(s[i]!=match[i]) return -1;    
        }
        for(int i=0;i<=temp.kind;i++)
        {
            ans+=abs(s[i]-match[i]);    
        }
    }
    else        
    {
        for(int i=temp.kind-5+1;i<5;i++)
        {
            if(s[i]!=match[i]) return -1;
        }
        for(int i=0;i<=temp.kind-5;i++)
        {
            ans+=abs(s[i]-match[i]);
        }
        ans+=abs(s[5]-match[5]);
    }
    return ans;
}

int bfs(int start)
{
    int ans=10000000;
    Node temp(start,0,0);
    queue<Node> que;
    que.push(temp);
    visit[temp.number][0]=1;
    
    while(!que.empty())
    {
        temp=que.front();
        que.pop();

        int number=temp.number,kind=temp.kind;
        int res=check(temp);    //中间密码up、down操作


        if(res!=-1) ans=min(ans,res+temp.step);    

        if(temp.step+1>=ans) continue;    //以后操作均是基于当前中间密码，若当前中间密码相比已搜索到的可行方案已不可能是最优操作方案则没有必要进行后续操作


        if(kind>0&&kind<=4)    //中间密码swap0操作

        {
            int newNumber=switchDigit(0,kind,number);
            if(!visit[newNumber][kind])
            {
                visit[newNumber][kind]=1;
                que.push(Node(newNumber,temp.step+1,kind));
            }
        }
        else if(kind>5)
        {
            int newNumber=switchDigit(0,kind-5,number);
            if(!visit[newNumber][kind])
            {
                visit[newNumber][kind]=1;
                que.push(Node(newNumber,temp.step+1,kind));
            }
        }

        if(kind<5)    //中间密码swap1操作

        {
            int newNumber=switchDigit(kind,5,number);
            if(!visit[newNumber][kind+5])
            {
                visit[newNumber][kind+5]=1;
                que.push(Node(newNumber,temp.step+1,kind+5));
            }
        }

        if(kind<5)    //中间密码right操作

        {
            if(!visit[number][kind+1])
            {
                visit[number][kind+1]=1;
                que.push(Node(number,temp.step+1,kind+1));
            }
        }
        else if(kind<9)
        {
            if(!visit[number][kind+1])
            {
                visit[number][kind+1]=1;
                que.push(Node(number,temp.step+1,kind+1));
            }
        }
            //没有必要进行left搜索，因为如果能通过左移某个密码来实现目标密码，则在访问那个密码之前一定先访问了其左移的密码

    }
    return ans;
}

int main()
{
    int v1,v2;
    scanf("%d%d",&v1,&v2);
    toArray(v2,match);
    printf("%d\n",bfs(v1));
    return 0;
}