2017ICPC南宁赛区网络赛 Minimum Distance in a Star Graph （bfs）

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 $SnS_{n}Sn, is an undirected graph consisting of n!n!n! nodes (or vertices) and ((n−1) ∗ n!)/2((n-1) * n!)/2((n−1) ∗ n!)/2 edges. Each node is uniquely assigned a label x1 x2 ... xnx_{1} x_{2} ... x_{n}x1 x2 ... xn which is any permutation of the n digits 1,2,3,...,n{1, 2, 3, ..., n}1,2,3,...,n. For instance, an S4S_{4}S4 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}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 x1 x2x3 x4 ... xnx_{1} x_{2} x_{3} x_{4} ... x_{n}x1 x2x3 x4 ... xn, it has n−1n-1n−1 edges connecting to nodes x2 x1 x3 x4 ... xnx_{2} x_{1} x_{3} x_{4} ... x_{n}x2 x1 x3 x4 ... xn, x3 x2 x1 x4 ... xnx_{3} x_{2} x_{1} x_{4} ... x_{n}x3 x2 x1 x4 ... xn, x4 x2 x3 x1 ... xnx_{4} x_{2} x_{3} x_{1} ... x_{n}x4 x2 x3 x1 ... xn, ..., and xn x2 x3 x4 ... x1x_{n} x_{2} x_{3} x_{4} ... x_{1}xn x2 x3 x4 ... x1. That is, the n−1n-1n−1 adjacent nodes are obtained by swapping the first symbol and the d−thd-thd−th symbol of x1 x2 x3 x4 ... xnx_{1} x_{2} x_{3} x_{4} ... x_{n}x1 x2 x3 x4 ... xn, for d=2,...,nd = 2, ..., nd=2,...,n. For instance, in S4S_{4}S4, node 123412341234 has 333 edges connecting to nodes 213421342134, 321432143214, and 423142314231. The following figure shows how S4S_{4}S4 looks (note that the symbols aaa, bbb, ccc, and ddd are not nodes; we only use them to show the connectivity between nodes; this is for the clarity of the figure).$

In this problem, you are given the following inputs:

Two nodes $x1x_{1}x1 x2x_{2}x2 x3x_{3}x3 ... xnx_{n}xn and y1y_{1}y1 y2y_{2}y2 y3 ... yny_{3} ... y_{n}y3 ... yn in SnS_{n}Sn.$

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

Input Format

A list of

Output Format

A list of

样例输入

样例输出

1
2
2
1
3

题目读完以后就是看看一个n位数能不能够通过题目中要求的变化变化到另一个n位数，求变化的最小次数。
用bfs搜索即可。
题目中要求的变化是指，将第一位数与之后的n-1位数分别交换得到的新数。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<queue>
 6 #include<map>
 7 using namespace std;
 8 int n,t;
 9 char ch1[15],ch2[15];
10 map<string,bool> mp;
11 struct node
12 {
13     string s;
14     int step;
15 };
16 int bfs()
17 {
18     queue<node> Q;
19     mp.clear();
20     node st;
21     st.s=ch1;
22     st.step=0;
23     Q.push(st);
24     while(!Q.empty())
25     {
26         node u=Q.front();
27         if (u.s==ch2) return u.step;
28         Q.pop();
29         for(int i=1; i<n; i++)
30         {
31             swap(u.s[0],u.s[i]);
32             if (mp[u.s]==1)
33             {
34                 swap(u.s[0],u.s[i]);
35                 continue;
36             }
37             mp[u.s]=1;
38             node ed;
39             ed.s=u.s;
40             ed.step=u.step+1;
41             Q.push(ed);
42             swap(u.s[0],u.s[i]);
43         }
44     }
45 }
46 int main()
47 {
48     scanf("%d",&n);
49     for(int t=1;t<=5;t++)
50     {
51         scanf("%s %s",&ch1,&ch2);
52         printf("%d
",bfs());
53     }
54     return 0;
55 }