能否给出一种方案,使得每行的元素从左到右递增,同一列的元素从上到下递增
扫描二维码
随时随地手机看文章
题意:
给定一个不规则的n行矩阵,每行分别有Ci个元素,其中Ci大于等于Ci+1,元素总个数为s,每个矩阵位置都有一个不同的值(从1到s),问能否给出一种方案,使得每行的元素从左到右递增,同一列的元素从上到下递增。
解题:
因为题目没限制最少需要几步,构造出一个合法解,只要求不超过s步,因为元素个数只有s个,我们只需要把元素按照1,2,3,...s的顺序排列,移到对应位置即可,最多只需要s-1步,故始终可以构造出一个合法解。
代码:
#include#include#include#includeusing namespace std; //node记录值为val的点的当前位置 struct node { int x,y,val; }store[3000]; //排序时按1,2,..s的方式排序 bool cmp(node a,node b) { return a.val<b.val; } //arr存储当前各位置存储的是什么数值 //c数组记录每行多少个元素 //x[i],y[i]数组分表表征值为i的点最后应该处于的位置 int arr[55][55],c[55],x[3000],y[3000]; //队列记录操作方式 queue q1,q2,q3,q4; int main() { //数据读入 int n,cnt=0,sum=0,tmp; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&c[i]); //数据处理 for(int i=1;i<=n;i++) { for(int j=1;j<=c[i];j++) { //分配每个值应处的位置 x[cnt+1]=i; y[cnt+1]=j; scanf("%d",&arr[i][j]); //记录某值当前的位置 store[cnt].val=arr[i][j]; store[cnt].x=i; store[cnt].y=j; cnt++; } //总元素个数,其实直接cnt就好 sum+=c[i]; } //按值从小到大排序 sort(store,store+sum,cmp); //开始为每个值挪位 for(int i=1;i<=sum;i++) { //如果该值已处于其应处的位置,则不操作 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要移过去的位置当前所占的值为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]); } } //输出,此处输出过于复杂,其实一个队列即可,一次弹出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; }