Cod sursa(job #330281)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 9 iulie 2009 13:27:57
Problema Grozavesti Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.81 kb
# include <stdio.h>
# include <stdlib.h>

const long int MAXN=301;
const long int MAXS=MAXN*MAXN;

long int n,a[MAXN][MAXN],vlen,usedc[MAXN],usedl[MAXN],sollen;
long int contentc[MAXN],contentl[MAXN],placec[MAXN],placel[MAXN];

typedef struct NODL
        {
        long int val,l,c;
        };
        
NODL v[MAXS];
struct {long int a,b; char op;} sol[MAXS];

int compara_NODL(const void *aa, const void *bb)
{
    NODL *a=(NODL*)aa;
    NODL *b=(NODL*)bb;
    if (a->val<b->val) return -1;
    if (a->val>b->val) return 1;
    if (a->l<b->l) return -1;
    if (a->l>b->l) return 1;
    if (a->c<b->c) return -1;
    if (a->c>b->c) return 1;
    return 0;
}

void citire()
{
     FILE *f=fopen("grozavesti.in","r");
     fscanf(f,"%ld",&n);
     long int i,j;
     for (i=1;i<=n;i++)
         for (j=1;j<=n;j++)
             {
             fscanf(f,"%ld",&a[i][j]);
             vlen++;
             v[vlen].l=i;
             v[vlen].c=j;
             v[vlen].val=a[i][j];
             }
     fclose(f);
     qsort(v+1,vlen,sizeof(NODL),compara_NODL);
     for (i=1;i<=n;i++)
         {
         placel[i]=i;
         placec[i]=i;
         contentc[i]=i;
         contentl[i]=i;
         }
}
             
void scrie()
{
     FILE *g=fopen("grozavesti.out","w");
     long int i;
     fprintf(g,"%ld\n",sollen);
     for (i=1;i<=sollen;i++)
         fprintf(g,"%c %ld %ld\n",sol[i].op,sol[i].a,sol[i].b);
     fclose(g);
}

void calculeaza()
{
    long int already=0,i=1;
    while (already<n)
          {
          if (!usedl[v[i].l]&&!usedc[v[i].c])
             {
             already++;
             //tre' sa aducem de pe linia v[i].l pe linia already
             if (placel[v[i].l]!=already)
                {
                sollen++;
                sol[sollen].op='L';
                //tre' sa interschimbam linia initiala 5 cu linia initiala 7;
                sol[sollen].a=placel[v[i].l];
                sol[sollen].b=already;
                placel[contentl[already]]=placel[v[i].l];
                contentl[placel[v[i].l]]=contentl[already];
                placel[v[i].l]=already;
                contentl[already]=v[i].l;
                }
             usedl[v[i].l]=1;
             if (placec[v[i].c]!=already)
                {
                sollen++;
                sol[sollen].op='C';
                sol[sollen].a=placec[v[i].c];
                sol[sollen].b=already;
                placec[contentc[already]]=placec[v[i].c];
                contentc[placec[v[i].c]]=contentc[already];
                placec[v[i].c]=already;
                contentc[already]=v[i].c;
                }
             usedc[v[i].c]=1;
             }
          i++;
          }
}

int main()
{
    citire();
    calculeaza();
    scrie();
    return 0;
}