能否給出一種方案，使得每行的元素從左到右遞增，同一列的元素從上到下遞增

題意：

??? 給定一個不規(guī)則的n行矩陣，每行分別有Ci個元素，其中Ci大于等于Ci+1，元素總個數(shù)為s，每個矩陣位置都有一個不同的值（從1到s），問能否給出一種方案，使得每行的元素從左到右遞增，同一列的元素從上到下遞增。

解題：

???? 因為題目沒限制最少需要幾步，構(gòu)造出一個合法解，只要求不超過s步，因為元素個數(shù)只有s個，我們只需要把元素按照1，2，3，...s的順序排列，移到對應(yīng)位置即可，最多只需要s-1步，故始終可以構(gòu)造出一個合法解。

代碼：

#include#include#include#includeusing?namespace?std;
//node記錄值為val的點的當(dāng)前位置
struct?node
{
	int?x,y,val;
}store[3000];
//排序時按1，2，..s的方式排序
bool?cmp(node?a,node?b)
{
	return?a.val<b.val;
}
//arr存儲當(dāng)前各位置存儲的是什么數(shù)值
//c數(shù)組記錄每行多少個元素
//x[i]，y[i]數(shù)組分表表征值為i的點最后應(yīng)該處于的位置
int?arr[55][55],c[55],x[3000],y[3000];
//隊列記錄操作方式
queue??q1,q2,q3,q4;
int?main()
{
	//數(shù)據(jù)讀入
	int?n,cnt=0,sum=0,tmp;
	scanf("%d",&n);
????for(int?i=1;i<=n;i++)
		scanf("%d",&c[i]);
	//數(shù)據(jù)處理
	for(int?i=1;i<=n;i++)
	{
		for(int?j=1;j<=c[i];j++)
		{
		???//分配每個值應(yīng)處的位置
		???x[cnt+1]=i;
		???y[cnt+1]=j;
???????????scanf("%d",&arr[i][j]);
		???//記錄某值當(dāng)前的位置
		???store[cnt].val=arr[i][j];
???????????store[cnt].x=i;
		???store[cnt].y=j;
		???cnt++;
		}
		//總元素個數(shù)，其實直接cnt就好
		sum+=c[i];
	}
	//按值從小到大排序
	sort(store,store+sum,cmp);
	//開始為每個值挪位
	for(int?i=1;i<=sum;i++)
	{
		//如果該值已處于其應(yīng)處的位置，則不操作
???????if(store[i-1].x==x[i]&&store[i-1].y==y[i])
		???continue;
	???else
	???{
		???//否則開始交換
??????????q1.push(store[i-1].x);
		??q2.push(store[i-1].y);
		??//i要移過去的位置當(dāng)前所占的值為v
		??int?v=arr[x[i]][y[i]];
		??//該位置分配給i
		??arr[x[i]][y[i]]=i;
		??//i原位置分配給v
		??arr[store[i-1].x][store[i-1].y]=v;
		??store[v-1].x=store[i-1].x;
		??store[v-1].y=store[i-1].y;
		??//記錄交換位置
		??q3.push(x[i]);
		??q4.push(y[i]);	??
	???}
	}
	//輸出，此處輸出過于復(fù)雜，其實一個隊列即可，一次彈出4個元素
	printf("%dn",q1.size());
	while(!q1.empty())
	{
		tmp=q1.front();
		q1.pop();
		printf("%d",tmp);
		tmp=q2.front();
		q2.pop();
		printf("?%d",tmp);
		tmp=q3.front();
		q3.pop();
		printf("?%d",tmp);
		tmp=q4.front();
		q4.pop();
		printf("?%dn",tmp);
	}
	return?0;
}