现有一个N! 个节点的图，每个节点的编号分别是编号（A1A2A3 …AN ）序列的一个排列。对于任意两个节点S 和T ，如果T 的编号是由S 编号的首位与除首位外的编号中任一位交换所得，则S 和T 之间有一条连线。请设计一个算法，求从节点S 走到节点（A1A2A3 …AN ）所需经过的最少边数。（N<=100）
- 输入
-
第一行为一个整数T，表示有T组测试数据。
对于每组测试数据：第一行是N ，第二行是节点S 的编号的下标（中间一个空格）。
- 输出
-
对于每组测试数据：输出一行，从S 到（A1A2A3 …AN ）所经过的最少边数。
- 样例输入
-
1 6 4 6 5 3 1 2
- 样例输出
-
6
#include <stdio.h>
main()
{
int number,te;
int n;
int a[101];
int i;
int sum;
int temp;
scanf("%d",&number);
for(te=1;te<=number;te++)
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
sum=0;
while(1)
{
for(i=0;i<n;i++)
{ if(a[i]==i+1)
continue;
else
break;
}
if(i==n)
break;
else
{
if(i==0)
{
temp=a[a[i]-1];
a[a[i]-1]=a[0];
a[0]=temp;
sum++;
}
else
{
temp=a[i];
a[i]=a[0];
a[0]=temp;
sum++;
}
}
}
printf("%d\n",sum);
}
}