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, an n?dimensional star graph, also referred to as S?n??, is an undirected graph consisting of n! nodes (or vertices) and ((n?1) ? n!)/2 edges. Each node is uniquely assigned a label x?1?? x?2?? ... x?n??which is any permutation of the n digits 1,2,3,...,n. For instance, an 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. For each node with label x?1?? x?2??x?3?? x?4?? ... x?n??, it has n?1 edges connecting to nodes x?2?? x?1?? x?3?? x?4?? ... x?n??, x?3?? x?2?? x?1?? x?4?? ... x?n??, x?4?? x?2?? x?3?? x?1?? ... x?n??, ..., and x?n?? x?2?? x?3?? x?4?? ... x?1??. That is, the n?1 adjacent nodes are obtained by swapping the first symbol and the d?th symbol of x?1?? x?2?? x?3?? x?4?? ... x?n??, for d=2,...,n. For instance, in S?4??, node 1234 has 3 edges connecting to nodes 2134, 3214, and 4231. The following figure shows how S?4?? looks (note that the symbols a, b, c, and d 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:
- n: the dimension of the star graph. We assume that n ranges from 4 to 9.
- Two nodes x?1?? x?2?? x?3?? ... x?n?? and y?1?? y?2?? y?3?? ... y?n?? in S?n??.
You have to calculate the distance between these two nodes (which is an integer).
Input Format
n (dimension of the star graph)
A list of 5 pairs of nodes.
Output Format
A list of 5 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;
}