Cod sursa(job #530629)

Utilizator nautilusCohal Alexandru nautilus Data 8 februarie 2011 09:15:45
Problema Grozavesti Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<fstream>
#define dmax 310
#define inf 1000010
using namespace std;

int n;
int a[dmax][dmax];
int mut;
int sol[dmax*2][5];


void citire()
{
 int i,j;
	
 ifstream fin("grozavesti.in");
 
 fin>>n;
 for (i=1; i<=n; i++)
	 {
	  a[i][0] = i;
	  for (j=1; j<=n; j++)
		  {
		   fin>>a[i][j];
		   a[0][j] = j;
		  }
	 }

 fin.close();
}


void solve()
{
 int k,lin,col;
 int min,minlin,mincol,minlin2,mincol2;
	
 for (k=1; k<=n; k++)
	 {
	  min=inf;
		 
	  for (lin=1; lin<=n; lin++)
		 if (a[lin][0] >= k)
			 for (col=1; col<=n; col++)
				 if (a[0][col] >= k)
					 if (a[a[lin][0]][a[0][col]] < min)
						 {
						  min = a[lin][col];
						  minlin = a[lin][0]; minlin2 = lin;
						  mincol = a[0][col]; mincol2 = col;
						 }
	  
	  if (minlin != k)
		  {
		   mut++;
		   sol[mut][1] = 1;
		   sol[mut][2] = k;
		   sol[mut][3] = minlin;
		  }
	  if (mincol != k)
		  {
		   mut++;
		   sol[mut][1] = 2;
		   sol[mut][2] = k;
		   sol[mut][3] = mincol;
		  }
	  
	  swap(a[k][0],a[minlin2][0]);
	  swap(a[0][k],a[0][mincol2]);
	 }
}


void afisare()
{
 int i;
	
 ofstream fout("grozavesti.out");
 
 fout<<mut<<'\n';
 for (i=1; i<=mut; i++)
	 {
	  if (sol[i][1] == 1)
		  fout<<"L "; else
		  fout<<"C ";
	  fout<<sol[i][2]<<" "<<sol[i][3]<<'\n';
	 }
 
 fout.close();
}


int main()
{
	
 citire();
 solve();
 afisare();
	
 return 0;
}