power oj/2360/Change

时间:2023-04-24 15:19:44

题目链接[https://www.oj.swust.edu.cn/problem/show/2360]

题意:给出两个四位数A、B,目地是用最少的步骤使A变成B。变换规则如下:1、相邻的两位数可以交换,消耗为1步。2、每位数字可以增加或者减小,步骤为增加或者减小的量。

题解:用DFS先全排列交换,然后对每一位进行增加或者减小记录步骤和,然后取最小值。

#include<bits/stdc++.h>
using namespace std;
int n[],m[];
bool vis[];
char s[];
int t,stp;
int check(int num)
{
int x[]={,num/,num%/,num%/,num%};
int p=;
for(int i = ;i <= ;i++)
{
p+=min(fabs(m[i]-x[i]),-fabs(m[i]-x[i]));
}
return p;
}
void DFS(int num,int ex)
{
if(num>)
{
printf("%d %d\n",num,ex);
stp=min(stp,check(num)+ex);
}
else
{
for(int i = ;i <= ;i++)
{
if(!vis[i])
{
vis[i] = ;
DFS(num*+n[i],ex++);
vis[i] = ;
}
}
}
}
int main ()
{
scanf("%d",&t);
while(t--)
{
stp=1e5;
scanf("%s",s+);
for(int i = ;i <= ;i++)
n[i] = s[i]-'';
scanf("%s",s+);
for(int i = ;i <= ;i++)
m[i] = s[i]-'';
DFS(,);
printf("%d\n",stp);
}
return ;
}