#include<iostream>
#include<queue>
#include<string>
#include<cstdio>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
typedef struct node
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
char data[5];
int step;
}Node;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
bool mark[11][11][11][11];
char a[5];
char b[5];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void Bfs()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i;
Node p,q;
queue<Node> Q;
memset(mark,0,sizeof(mark));
strcpy(p.data,a);
p.step = 0;
Q.push(p);
mark[p.data[0]-'0'][p.data[1]-'0'][p.data[2]-'0'][p.data[3]-'0'] = 1;
while(!Q.empty())
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
q = Q.front();
Q.pop();
for(i=0;i<4;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
strcpy(p.data,q.data);
p.step=0;
p.data[i] = q.data[i]+1;
if(p.data[i] == '9' +1 )
p.data[i] = '1';
p.step = q.step+1;
if(mark[p.data[0]-'0'][p.data[1]-'0'][p.data[2]-'0'][p.data[3]-'0'] == 0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(strcmp(p.data,b) == 0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
cout<<p.step<<endl;
return ;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
mark[p.data[0]-'0'][p.data[1]-'0'][p.data[2]-'0'][p.data[3]-'0'] = 1;
Q.push(p);
}
}
strcpy(p.data,q.data);
p.step=0;
p.data[i] = q.data[i]-1;
if(p.data[i] == '0' )
p.data[i] = '9';
p.step = q.step+1;
if(mark[p.data[0]-'0'][p.data[1]-'0'][p.data[2]-'0'][p.data[3]-'0'] == 0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(strcmp(p.data,b) == 0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
cout<<p.step<<endl;
return ;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
mark[p.data[0]-'0'][p.data[1]-'0'][p.data[2]-'0'][p.data[3]-'0'] = 1;
Q.push(p);
}
}
if(i<3)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
strcpy(p.data,q.data);
p.step=0;
p.data[i] = q.data[i+1];
p.data[i+1] = q.data[i];
p.step = q.step+1;
if(mark[p.data[0]-'0'][p.data[1]-'0'][p.data[2]-'0'][p.data[3]-'0'] == 0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(strcmp(p.data,b) == 0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
cout<<p.step<<endl;
return ;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
mark[p.data[0]-'0'][p.data[1]-'0'][p.data[2]-'0'][p.data[3]-'0'] = 1;
Q.push(p);
}
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int text;
cin>>text;
while(text--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%s",a);
scanf("%s",b);
if(strcmp(a,b) == 0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
cout<<0<<endl;
continue;
}
Bfs();
}
return 0;
}