#include <stdio.h>

int x[50][50], swap[50][50], m, r[50], re[50], k, i, min;

void sort(int k)
{
	int i, j, min, poz, c;
	for(i=0;i<m-1;i++) {
		poz=i;
		min=x[k][i];
		for(j=i+1;j<m;j++)
			if(min>x[k][j]) {
				poz=j;
				min=x[k][j];
			}
		c=x[k][i];
		x[k][i]=x[k][poz];
		x[k][poz]=c;
	}
}

void citire()
{
	int i, j;
	printf("m="); scanf("%i", &m);
	for(j=0;j<m;j++) {
		for(i=0;i<m;i++) {
			printf("x[%i][%i]=", j, i); scanf("%i", &x[j][i]);
		}
		printf("\n");
	}
}

void afis()
{
	int i, j;
	for(j=0;j<m;j++) {
		for(i=0;i<m;i++) printf("%4i ", x[j][i]);
		printf("\n");
	}
	printf("\n");
}

void afis2()
{
	int i, j;
	for(j=0;j<m;j++) {
		for(i=0;i<m;i++) printf("%4i ", x[re[j]][i]);
		printf("\n");
	}
	printf("\n");
}

int sumaDiag()
{
	int s=0, i;
	for(i=0;i<m;i++) s+=x[r[i]][i];
	return s;
}

int caut(int k) 
{
	for(i=0;i<k;i++)
		if(r[i]==r[k]) return 0;
	return 1;
}

void back()
{
	k=0;
	for(i=0;i<m;i++) r[i]=-1;
	while(k>-1) {
		while(r[k]<m-1) {
			r[k]++;
			if(caut(k)) k++;
			if(k==m) { 
				if(min>sumaDiag()) {
					min=sumaDiag();
					for(i=0;i<m;i++) re[i]=r[i];
				}
				k--;
			}
		}
		r[k]=-1;
		k--;
	}
}

void ini()
{
	min=0;
	for(i=0;i<m;i++) {
		re[i]=i;
		min+=x[i][i];
	}
}

void main()
{
	citire();
	printf("Afiseaza matricea :\n");afis();
	for(int i=0; i< m; i++) sort(i);
	printf("Afiseaza matricea sortata:\n");afis();
	ini();
	back();
	printf("Afiseaza matricea ordonata dupa criteriul 2:\n");afis2();
	printf("Suma pe diagonala minima este %i\n", min);
}