2017 ACM-ICPC 亚洲区（南宁赛区）网络赛 J. Minimum Distance in a Star Graph（bfs+状态保存）

Bertha 。 2022-06-08 11:38 172阅读 0赞

In this problem, we will define a graph called star graph, and the question is to find the minimum distance between two given nodes in the star graph.

Given an integer n*n*, an n-dimensional*n*−*d**i**m**e**n**s**i**o**n**a**l* star graph, also referred to as S\_\{n\}*S**n*, is an undirected graph consisting of n!*n*! nodes (or vertices) and ((n-1)\\ \*\\ n!)/2((*n*−1)∗*n*!)/2 edges. Each node is uniquely assigned a label x\_\{1\}\\ x\_\{2\}\\ ...\\ x\_\{n\}*x*1*x*2...*x**n*which is any permutation of the n digits \{1, 2, 3, ..., n\}1,2,3,...,*n*. For instance, an S\_\{4\}*S*4 has the following 24 nodes \{1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321\}1234,1243,1324,1342,1423,1432,2134,2143,2314,2341,2413,2431,3124,3142,3214,3241,3412,3421,4123,4132,4213,4231,4312,4321. For each node with label x\_\{1\}\\ x\_\{2\} x\_\{3\}\\ x\_\{4\}\\ ...\\ x\_\{n\}*x*1*x*2*x*3*x*4...*x**n*, it has n-1*n*−1 edges connecting to nodes x\_\{2\}\\ x\_\{1\}\\ x\_\{3\}\\ x\_\{4\}\\ ...\\ x\_\{n\}*x*2*x*1*x*3*x*4...*x**n*, x\_\{3\}\\ x\_\{2\}\\ x\_\{1\}\\ x\_\{4\}\\ ...\\ x\_\{n\}*x*3*x*2*x*1*x*4...*x**n*, x\_\{4\}\\ x\_\{2\}\\ x\_\{3\}\\ x\_\{1\}\\ ...\\ x\_\{n\}*x*4*x*2*x*3*x*1...*x**n*, ..., and x\_\{n\}\\ x\_\{2\}\\ x\_\{3\}\\ x\_\{4\}\\ ...\\ x\_\{1\}*x**n**x*2*x*3*x*4...*x*1. That is, the n-1*n*−1 adjacent nodes are obtained by swapping the first symbol and the d-th*d*−*t**h* symbol of x\_\{1\}\\ x\_\{2\}\\ x\_\{3\}\\ x\_\{4\}\\ ...\\ x\_\{n\}*x*1*x*2*x*3*x*4...*x**n*, for d = 2, ..., n*d*=2,...,*n*. For instance, in S\_\{4\}*S*4, node 12341234 has 33 edges connecting to nodes 21342134, 32143214, and 42314231. The following figure shows how S\_\{4\}*S*4 looks (note that the symbols a*a*, b*b*, c*c*, and d*d* are not nodes; we only use them to show the connectivity between nodes; this is for the clarity of the figure).

[![b9510b5515aa0293915340ea604adac52bc73f30.png][]][b9510b5515aa0293915340ea604adac52bc73f30.png]

In this problem, you are given the following inputs:

*  n*n*: the dimension of the star graph. We assume that n*n* ranges from 44 to 99.
 *  Two nodes x\_\{1\}*x*1 x\_\{2\}*x*2 x\_\{3\}*x*3 ... x\_\{n\}*x**n* and y\_\{1\}*y*1 y\_\{2\}*y*2 y\_\{3\}\\ ...\\ y\_\{n\}*y*3...*y**n* in S\_\{n\}*S**n*.

You have to calculate the distance between these two nodes (which is an integer).

### Input Format ###

n*n* (dimension of the star graph)

A list of 55 pairs of nodes.

### Output Format ###

A list of 55 values, each representing the distance of a pair of nodes.

#### 样例输入 ####

4
    1234 4231
    1234 3124
    2341 1324
    3214 4213
    3214 2143

#### 样例输出 ####

1
    2
    2
    1
    3

题解：

题意：

给一个全排序，每次允许第一个数字和后面的随便一个数字交换，让你求可以达到目标串的最小交换次数

题解：

一开始从后往前放wa了几发，后来发现9的阶乘是36w左右，满足bfs的时间复杂度，然后就bfs+状态判断ac了

代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    #define ll long long
    #define INF 1008611111
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    using namespace std;
    struct node
    {
        ll v;
        int step;
    };
    queue<node>q;
    map<ll,int>p;
    int a[15];
    int b[15];
    int main()
    {
        int test,n,i,j;
        ll tar,cur;
        node now,next;
        scanf("%d",&n);
        test=5;
        while(test--)
        {
            scanf("%lld%lld",&tar,&cur);
            p.clear();
            if(tar==cur)
            {
                printf("0\n");
                continue;
            }
            while(!q.empty())
                q.pop();
            now.v=cur;
            now.step=0;
            p[now.v]=1;
            q.push(now);
            int t;
            while(!q.empty())
            {
                now=q.front();
                q.pop();
                for(i=0;i<n;i++)
                {
                    a[n-i-1]=now.v%10;
                    b[n-i-1]=a[n-i-1];
                    now.v/=10;
                }
                for(i=1;i<n;i++)
                {
                    swap(b[0],b[i]);
                    next.v=0;
                    for(j=0;j<n;j++)
                    {
                        next.v=next.v*10+b[j];
                        b[j]=a[j];
                    }
                    if(!p[next.v])
                    {
                        p[next.v]=1;
                        next.step=now.step+1;
                        if(next.v==tar)
                        {
                            t=next.step;
                            goto loop;
                        }
                        q.push(next);
                    }
                }
            }
            loop:;
            printf("%d\n",t);
        }
        return 0;
    }

[b9510b5515aa0293915340ea604adac52bc73f30.png]: /images/20220608/ff3b9f06d3394de8b060c8aceecf205b.png