2416 参考答案

返回“大学生程序设计竞赛”

/*
zju 2416  BFS
ymc 2008/5/21
题目大意：
数的转换，输入两个数，求第一个数转到第二个数的最快转换方法（最小步数）。
转换规则：
1，从1个数转到下一个数或前一个数，（1的前一个数是9，9的后一个数是1）
2，相邻的数可以互相转换，最左边的数和最右边的数不相邻。
进行一次转换算一步。

*/
#include <iostream>
#include <queue>
using namespace std;
const int N=10000;
bool used[N];
queue<int> a;
queue<int> b;
int tran[11]={9,1,2,3,4,5,6,7,8,9,1};
int bit[4];
void addtob(int u)
{

    int next;
    int tmp=u;
    for(int i=3;i>=0;i--)
    {
        bit[i]=tmp%10;
        tmp=tmp/10;
    }
    for(int i=0;i<=3;i++)
    {
        tmp=bit[i];
        bit[i]=tran[bit[i]+1];
        next=1000*bit[0]+100*bit[1]+10*bit[2]+bit[3];
        if(!used[next]) { b.push(next);used[next]=true;}
        bit[i]=tmp;
        bit[i]=tran[bit[i]-1];
        next=1000*bit[0]+100*bit[1]+10*bit[2]+bit[3];
        if(!used[next]) { b.push(next);used[next]=true;}
        bit[i]=tmp;
    }
    next=1000*bit[1]+100*bit[0]+10*bit[2]+bit[3];
    if(!used[next]) { b.push(next);used[next]=true;}

    next=1000*bit[0]+100*bit[2]+10*bit[1]+bit[3];
    if(!used[next]) { b.push(next);used[next]=true;}

    next=1000*bit[0]+100*bit[1]+10*bit[3]+bit[2];
    if(!used[next]) { b.push(next);used[next]=true;}
}
int BFS(int n,int m)
{
    while(!a.empty())
        a.pop();
    while(!b.empty())
        b.pop();
    memset(used,0,sizeof(used));
    a.push(n);
    used[n]=true;
    int ans=0;
    int u;
    while(1)
    {
        while(!a.empty())
        {
            u=a.front();
            if(u==m) return ans;
            a.pop();
            addtob(u);
        }
        while(!b.empty())
        {
            u=b.front();
            b.pop();
            a.push(u);
        }
        ans++;
    }
}
int main()
{
    int test;
    cin>>test;
    int n,m;
    while(test-->0)
    {
        cin>>n>>m;
        cout<<BFS(n,m)<<endl;
    }
}

/*
zju 2416  BFS
ymc 2008/5/21
题目大意：
数的转换，输入两个数，求第一个数转到第二个数的最快转换方法（最小步数）。
转换规则：
1，从1个数转到下一个数或前一个数，（1的前一个数是9，9的后一个数是1）
2，相邻的数可以互相转换，最左边的数和最右边的数不相邻。
进行一次转换算一步。
分析与解题思路：

*/
#include <iostream>
#include <queue>
using namespace std;
const int N=10000;
bool used[N];
queue<int> a;
queue<int> b;
void addtob(int u)
{
    int t,x,y,z;
    int next;
    int tmp=u;
    z=tmp%10;tmp=tmp/10;
    y=tmp%10;tmp=tmp/10;
    x=tmp%10;
    t=tmp/10;

    if(t==9) next=u-8000;//第1位加1
    else next=u+1000;
    if(!used[next]) { b.push(next);used[next]=true;}

    if(x==9) next=u-800;  //第2位加1
    else    next=u+100;
    if(!used[next]) { b.push(next);used[next]=true;}

    if(y==9) next=u-80;  //第3位加1
    else    next=u+10;
    if(!used[next]) { b.push(next);used[next]=true;}

    if(z==9)  next=u-8; //第4位加1
    else    next=u+1;
    if(!used[next]) { b.push(next);used[next]=true;}

    if(t==1) next=u+8000;//第1位减1
    else next=u-1000;
    if(!used[next]) { b.push(next);used[next]=true;}

    if(x==1) next=u+800;  //第2位减1
    else    next=u-100;
    if(!used[next]) { b.push(next);used[next]=true;}

    if(y==1) next=u+80;  //第3位减1
    else    next=u-10;
    if(!used[next]) { b.push(next);used[next]=true;}

    if(z==1)  next=u+8;  //第4位减1
    else    next=u-1;
    if(!used[next]) { b.push(next);used[next]=true;}

    next=x*1000+t*100+10*y+z;  //1,2
    if(!used[next]) { b.push(next);used[next]=true;}

    next=1000*t+y*100+x*10+z; //2,3
    if(!used[next]) { b.push(next);used[next]=true;}

    next=1000*t+x*100+z*10+y; //3,4
    if(!used[next]) { b.push(next);used[next]=true;}

}
int BFS(int n,int m)
{
    while(!a.empty())
        a.pop();
    while(!b.empty())
        b.pop();
    memset(used,0,sizeof(used));
    a.push(n);
    used[n]=true;
    int ans=0;
    int u;
    while(1)
    {
        while(!a.empty())
        {
            u=a.front();
            if(u==m) return ans;
            a.pop();
            addtob(u);
        }
        while(!b.empty())
        {
            u=b.front();
            b.pop();
            a.push(u);
        }
        ans++;
    }
}
int main()
{
    int test;
    cin>>test;
    int n,m;
    while(test-->0)
    {
        cin>>n>>m;
        cout<<BFS(n,m)<<endl;
    }
}