/*
 * Problema 6.17 do carderno de Exercicios: Quadrado Latino
 *
 * Dizemos que uma matriz nxn A é um quadrado latino de ordem n se em cada linha
 * e em cada coluna aparecem todos os inteiros 1,2,3,...,n (ou seja, cada linha
 * e coluna é permutação dos inteiros 1,2,...,n).  
 *
 * (a) Escreva uma função que recebe como parâmetros um inteiro n, um vetor V
 * com n inteiros e verifica se em V ocorrem todos os inteiros de 1 a n.   
 *
 * (b) Usando a função acima, verifique se uma dada matriz inteira Anxn é um
 * quadrado latino de ordem n.   
 *
 */

#include <stdio.h>

#define NMAX  100
#define TRUE    1
#define FALSE   0

/*
 * Leitura de uma matriz inteira mat de dimensao nlinhas x ncolunas
 */
void lematriz(int mat[][NMAX], int nlinhas, int ncolunas)
{
  int i, j;

  for (i = 0; i < nlinhas; i++) {
    /* leitura da i-esima linha */
    printf("Entre com os elementos da linha no. %d\n", i + 1);
    for (j = 0; j < ncolunas; j++)
      scanf("%d", &mat[i][j]);	/* nao esqueca o '&'! */
  }
}

/*
 * Imprime uma matriz mat de dimensao nlinhas x ncolunas
 */
void imprimematriz(int mat[][NMAX], int nlinhas, int ncolunas)
{
  int i, j;

  for (i = 0; i < nlinhas; i++) {
    /* imprime a i-esima linha */
    for (j = 0; j < ncolunas; j++)
      printf("%4d", mat[i][j]);
    /* muda de linha */
    printf("\n");
  }
}

/* Funcao que ordena um vetor inteiro dado */

void ordene_vetor(int v[], int n)
{
  int i, j, min, index_min;

  for (i = 0; i < n - 1; i++) {
    min = v[i];
    index_min = i;

    for (j = i + 1; j < n; j++)
      if (v[j] < min) {
	min = v[j];
	index_min = j;
      }
    v[index_min] = v[i];
    v[i] = min;
  }
}

/* 
 * Funcao que recebe como parametros um vetor v e um inteiro n 
 * e retorna TRUE (1) se todos os inteiros entre 1 e n ocorrem nas
 * n primeiras posicoes do vetor v, caso contrario a funcao 
 * retorna FALSE (0).
 */

int elatina(int v[], int n)
{
  int i, w[NMAX];

  for (i = 0; i < n; i++)
    w[i] = v[i];

  ordene_vetor(w, n);

  for (i = 0; i < n; i++)
    if (w[i] != i + 1)
      return FALSE;

  return TRUE;
}

/* 
 * M A I N 
 */

int main()
{
  int i, j, n, equadlatino, v[NMAX], m[NMAX][NMAX];

  printf("Entre com a dimensao da matriz: ");
  scanf("%d", &n);

  lematriz(m, n, n);
  printf("\n\nMatriz lida:\n");
  imprimematriz(m, n, n);

  equadlatino = TRUE;		/* a matriz e' um quadrado latino ate' que 
				 * se prove o contrario
				 */
  for (i = 0; i < n && equadlatino == TRUE; i++)
    /* verifica se a linha m[i] da matriz e' "latina" */
    equadlatino = elatina(m[i], n);

  for (j = 0; j < n && equadlatino == TRUE; j++) {
    /* verifica se a coluna j da matriz m e' "latina" */
    /* copia coluna j para o vetor auxiliar v */
    for (i = 0; i < n; i++)
      v[i] = m[i][j];

    equadlatino = elatina(v, n);
  }

  if (equadlatino == TRUE)
    printf("\n\nA matriz e' um quadrado latino.\n");
  else
    printf("\n\nA matriz nao e' um quadrado latino.\n");

  return 0;
}