传送门： 点击打开链接
题目大意：给你2个四位数的数字，要求把上面那个转变成下面那个。转换规则：每个位置的数字每次只能+1或-1，或者和相邻的位置的数字交换，这里不存在第一个和最后一个交换的情况。问最少需要多少步数。
解题思路：由于求最短交换步数，用bfs搜索。46ms时间。这里有个进阶的做法：双向搜索。什么是双向搜索呢？就是利用bfs的特性，每次一层一层地搜索。一个循环从正向搜索，一个循环从终点过来反向搜索，当然当两个搜索碰面的地方就是最优解（这个最优解要把两个方向的步数相加）。注意一点的是在每次走过的地方你要在这个点标记一下，并且保存当前的步数，这里的标记要区分是正向和反向，当你搜索的时候发现改点已被不同于本次搜索方向的搜过了（相当于起点和终点已经连成一条线了），结束搜索。双向搜索发现在数据图越大的时候越高效，0ms时间。
单向BFS AC代码：
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct node
{
char s[5];
int step;
};
char t1[5],t2[5],ch;
int book[10][10][10][10];
queue<node> que;
int bfs()
{
node now,xia;
int i;
while(!que.empty())
que.pop();
book[t1[0]-'0'][t1[1]-'0'][t1[2]-'0'][t1[3]-'0']=1;
strcpy(now.s,t1);
now.step=0;
que.push(now);
while(!que.empty())
{
now=que.front();
que.pop();
if(!strcmp(now.s,t2))
return now.step;
for(i=0;i<4;i++) //+
{
xia=now;
if(now.s[i]=='9')
xia.s[i]='1';
else
xia.s[i]=now.s[i]+1;
if(book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'])
continue;
xia.step=now.step+1;
book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0']=1;
que.push(xia);
}
for(i=0;i<4;i++) //-
{
xia=now;
if(now.s[i]=='1')
xia.s[i]='9';
else
xia.s[i]=now.s[i]-1;
if(book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'])
continue;
xia.step=now.step+1;
book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0']=1;
que.push(xia);
}
for(i=0;i<3;i++) //swap
{
xia=now;
ch=xia.s[i];
xia.s[i]=xia.s[i+1];
xia.s[i+1]=ch;
if(book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'])
continue;
xia.step++;
book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0']=1;
que.push(xia);
}
}
return 0;
}
int main()
{
int t;
scanf("%d ",&t);
while(t--)
{
scanf("%s%s",t1,t2);
memset(book,0,sizeof(book));
cout<<bfs()<<endl;
}
return 0;
}#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct node
{
char s[5];
int step;
};
char t1[5],t2[5],ch;
int book[10][10][10][10][2];
queue<node> que;
queue<node> Q;
int bfs()
{
node now,xia,NOW;
int i,s=0;
while(!que.empty())
que.pop();
while(!Q.empty())
Q.pop();
book[t1[0]-'0'][t1[1]-'0'][t1[2]-'0'][t1[3]-'0'][0]=1;
book[t2[0]-'0'][t2[1]-'0'][t2[2]-'0'][t2[3]-'0'][0]=2;
book[t1[0]-'0'][t1[1]-'0'][t1[2]-'0'][t1[3]-'0'][1]=0;
book[t2[0]-'0'][t2[1]-'0'][t2[2]-'0'][t2[3]-'0'][1]=0;
strcpy(now.s,t1);
strcpy(NOW.s,t2);
now.step=0;
NOW.step=0;
que.push(now);
Q.push(NOW);
while(!que.empty() && !Q.empty())
{
while(que.front().step==s)
{
now=que.front();
que.pop();
for(i=0;i<4;i++) //+
{
xia=now;
xia.step=now.step+1;
if(now.s[i]=='9')
xia.s[i]='1';
else
xia.s[i]=now.s[i]+1;
if(book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][0]==1)
continue;
if(book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][0]==2)
return xia.step+book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][1];
book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][0]=1;
book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][1]=xia.step;
que.push(xia);
}
for(i=0;i<4;i++) //-
{
xia=now;
xia.step=now.step+1;
if(now.s[i]=='1')
xia.s[i]='9';
else
xia.s[i]=now.s[i]-1;
if(book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][0]==1)
continue;
if(book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][0]==2)
return xia.step+book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][1];
book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][0]=1;
book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][1]=xia.step;
que.push(xia);
}
for(i=0;i<3;i++) //swap
{
xia=now;
xia.step=now.step+1;
ch=xia.s[i];
xia.s[i]=xia.s[i+1];
xia.s[i+1]=ch;
if(book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][0]==1)
continue;
if(book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][0]==2)
return xia.step+book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][1];
book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][0]=1;
book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][1]=xia.step;
que.push(xia);
}
}
while(Q.front().step==s)
{
now=Q.front();
Q.pop();
for(i=0;i<4;i++) //+
{
xia=now;
xia.step=now.step+1;
if(now.s[i]=='9')
xia.s[i]='1';
else
xia.s[i]=now.s[i]+1;
if(book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][0]==2)
continue;
if(book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][0]==1)
return xia.step+book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][1];
book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][0]=2;
book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][1]=xia.step;
Q.push(xia);
}
for(i=0;i<4;i++) //-
{
xia=now;
xia.step=now.step+1;
if(now.s[i]=='1')
xia.s[i]='9';
else
xia.s[i]=now.s[i]-1;
if(book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][0]==2)
continue;
if(book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][0]==1)
return xia.step+book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][1];
book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][0]=2;
book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][1]=xia.step;
Q.push(xia);
}
for(i=0;i<3;i++) //swap
{
xia=now;
xia.step=now.step+1;
ch=xia.s[i];
xia.s[i]=xia.s[i+1];
xia.s[i+1]=ch;
if(book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][0]==2)
continue;
if(book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][0]==1)
return xia.step+book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][1];
book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][0]=2;
book[xia.s[0]-'0'][xia.s[1]-'0'][xia.s[2]-'0'][xia.s[3]-'0'][1]=xia.step;
Q.push(xia);
}
}
s++;
}
return 0;
}
int main()
{
int t;
scanf("%d ",&t);
while(t--)
{
scanf("%s%s",t1,t2);
memset(book,0,sizeof(book));
cout<<bfs()<<endl;
}
return 0;
}
京公网安备 11010502036488号