uva331

題目意思比較難懂（英文水準較菜），先翻譯一下關鍵内容吧。

交換一個數組的相鄰兩個元素可以達到對數組排序的功能，類似于冒泡排序，但交換的方案可能不止一種。比如說數組A【3】為3,2,1，要想排為1,2,3，可以先交換位置1和2的元素（數組變為2，3，1），然後交換位置2和3的元素（變為2，1，3），最後交換位置1和2的（變為1，2，3），此為方案一，具體可以用1,2,1（數字即每次交換的第一個數的位置）來描述。當然還可以先交換位置2和3（312），然後交換位置1和2（132）最後交換位置2和3（123），如上的描述方法便是2,1,2，此為方案二。當然這樣的方案是無窮多的，比如1，1，2，1，2同樣可以實作排序，但這種情況下前兩次交換是在做無用功，不是移動次數最小的方案。此題要求出移動次數最少的方案有多少個，如例子中的情況就隻有2種方案。

了解了題意就不難做了，還是繼續回溯，達到順序後方案數加1，如果一開始就是順序的話則不進行深搜。

#include<iostream>

using namespace std;

int n,result,data[5];

bool isorder()
{
	for (int i=0;i<n-1;i++)
		if (data[i]>data[i+1])
			return false;
	return true;
}
void dfs()
{
	int tmp,i;
	if (isorder())
		result++;
	else
	{
		for(i=0;i<n-1;i++)
		{
			if (data[i]>data[i+1])
			{
				tmp=data[i];data[i]=data[i+1];data[i+1]=tmp;
				dfs();
				tmp=data[i];data[i]=data[i+1];data[i+1]=tmp;
			}
		}
	}

}
int main()
{
	int col=0;
	while (cin>>n&&n)
	{
		col++;
		for (int i=0;i<n;i++)
			cin>>data[i];
		result=0;
		if (!isorder())
			dfs();
		cout<<"There are "<<result<<" swap maps for input data set "<<col<<"."<<endl;

	}
	return 0;
}