power oj/2360/Change

题目链接[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[15],m[15];
bool vis[15];
char s[15];
int t,stp;
int check(int num)
{
    int x[10]={0,num/1000,num%1000/100,num%100/10,num%10};
    int p=0;
    for(int i = 1;i <= 4;i++)
    {
        p+=min(fabs(m[i]-x[i]),9-fabs(m[i]-x[i]));
    }
    return p;
}
void DFS(int num,int ex)
{
    if(num>999)
    {
        printf("%d %d
",num,ex);
        stp=min(stp,check(num)+ex);
    }
    else
    {
        for(int i = 1;i <= 4;i++)
        {
            if(!vis[i])
            {
                vis[i] = 1;
                DFS(num*10+n[i],ex++);
                vis[i] = 0;
            }
        }
    }
}
int main ()
{
    scanf("%d",&t);
    while(t--)
    {
        stp=1e5;
        scanf("%s",s+1);
        for(int i = 1;i <= 4;i++)
            n[i] = s[i]-'0';
        scanf("%s",s+1);
        for(int i = 1;i <= 4;i++)
            m[i] = s[i]-'0';
        DFS(0,0);
        printf("%d
",stp);
    }
    return 0;
}