escola
import java.util.Random;
import java.util.Calendar;
import java.util.Date;
public class Matriz {
    private int linhas;
    private int colunas;
    private int[][] mat;


Matriz(int novaLinhas, int novaColunas){
    this.setLinhas(novaLinhas);
    this.setColunas(novaColunas);
    this.mat= new int[this.getLinhas()][this.getColunas()];
}
public void setLinhas(int novaLinhas){
    this.linhas=novaLinhas;

}
public int getLinhas(){
    return this.linhas;
}
public void setColunas(int novaColunas){
    this.colunas=novaColunas;
}
public int getColunas(){
    return this.colunas;
}
 public void setElemento(int i, int j, int novoElemento){
        this.mat[i][j] = novoElemento;
        }
  public int getElemento(int i, int j){
      return this.mat[i][j];
  }
public void inicializador(int novoElemento){

        for(int i = 0; i < this.getLinhas(); i++){
            for(int j = 0; j < this.getColunas(); j++){
                this.setElemento(i, j, novoElemento);
            }
        }
    }


public void inicializaRandomico(){
    Random rand = new Random();

    for(int i=0; i<getLinhas(); i++){
       for(int j=0; j<getColunas(); j++){
          this.setElemento(i,j,rand.nextInt(getLinhas()*getColunas() ));


        }
    }
}

public void imprimidorMatriz(){
   if(this.retorneOrdem()!=-1){
    for(int i = 0; i < this.getLinhas(); i++){
            System.out.printf("\n|");
            for(int j = 0; j < this.getColunas(); j++){
                System.out.printf(" %d |",this.getElemento(i,j));
            }
        }
    }
   if(this.retorneOrdem()==-1){
       System.out.println("Nao foi possivel executar o programa, pois a matriz nao eh quadrada.");
    }
}

	public int retorneOrdem(){
		int numL, numC, ordem,aux;

		numL = this.getLinhas();
		numC = this.getColunas();
		ordem = -1;
		if(numL == numC){
			ordem = numL;

                }


		return ordem;
	}

    public int detOrdem1(Matriz matN, int i, int j){
        return matN.getElemento(i,j);
    }

    public int detOrdem2(Matriz matN, int i, int j){
        int diagonalP, diagonalI,detResposta;

        diagonalP = matN.detOrdem1(matN,i,j) * matN.detOrdem1(matN,i+1,j+1);
        diagonalI = matN.detOrdem1(matN,i,j+1) * matN.detOrdem1(matN,i+1,j);
        detResposta=diagonalP - diagonalI;
        return (detResposta);
    }

    public int determinante(){
        int aux = 0;

        if(this.retorneOrdem()!=1){
            aux = this.detRecursivo(this, this.getLinhas());
        }
        return aux;
    }

    public int determinanteComSwitch(Matriz mat, int ordem){
        int armazenador = 0;
        switch(ordem){
            case 1:
                armazenador = mat.detOrdem1(mat,0,0);
                break;
            case 2:
                armazenador = mat.detOrdem2(mat,0,0);
                break;
            default:
                armazenador = mat.detLaplace(mat,ordem);
                break;
        }
        return armazenador;
    }
   public void copiaMatrizOK(Matriz mat1, Matriz mat2, int isqn, int jsqn){
		int i_alvo = 0, j_alvo, i_original, j_original, aux;

			for (i_original = 0; i_original < mat1.getLinhas(); i_original++){
				if (i_original != isqn){
					j_alvo = 0;
					for(j_original = 0; j_original < mat1.getLinhas(); j_original++){
						if (j_original != jsqn){
							aux = mat1.getElemento(i_original,j_original);
							mat2.setElemento(i_alvo,j_alvo,aux);
							j_alvo++;
						}
					}
					i_alvo++;
				}
			}
	}

  	public void copiaMatriz(Matriz mat, Matriz mat2, int isqn, int jsqn){
		Matriz matrizOriginal, matrizAlvo;
		int ordem_Max, ordem_Min;
		if(((mat!=null) && (mat2 != null)) && (mat.retorneOrdem()!=1 && mat2.retorneOrdem()!=1)){
			ordem_Max = mat.getLinhas();
            ordem_Min = mat2.getLinhas();
            matrizOriginal = mat;
			matrizAlvo = mat2;
			if(ordem_Max < ordem_Min){
				ordem_Max = mat2.getLinhas();
                ordem_Min = mat.getLinhas();
                matrizOriginal = mat2;
				matrizAlvo = mat;
			}
			if(((isqn < ordem_Max) && (jsqn < ordem_Max)) && ((ordem_Max - ordem_Min) == 1)){
				this.copiaMatrizOK(matrizOriginal,matrizAlvo,isqn,jsqn);
			}
		}
	}


    public int detRecursivo(Matriz mat, int ordem){
        int determinante = 0;
        switch(ordem){
            case 1:
                determinante = mat.detOrdem1(mat,0,0);
                break;
            case 2:
                determinante = mat.detOrdem2(mat,0,0);
                break;
            default:
                determinante = mat.detLaplace(mat,ordem);
                break;
        }
        return determinante;
    }


    public int detOtimizado(){
        int aux = 0;

        if(this.retorneOrdem()!=1){
            aux = this.detRecursivoOtimizado(this, this.getLinhas());

        }
        return aux;
    }
    public int detRecursivoOtimizado(Matriz mat, int ordem){
        int detResposta = 0;
        switch(ordem){
            case 1:
                detResposta = mat.detOrdem1(mat,0,0);
                break;
            case 2:
                detResposta = mat.detOrdem2(mat,0,0);
                break;
            default:
                detResposta = mat.detLaplaceOtimizado(mat,ordem);
                break;
        }
            return detResposta;

}


    public int detLaplace(Matriz mat, int ordem){
        Matriz matAux = new Matriz(ordem-1,ordem-1);
        int somaDet = 0;

        for(int j = 0; j < ordem; j++){
            mat.copiaMatriz(mat,matAux,0,j);
            somaDet = somaDet + (Cofator(0,j) * mat.getElemento(0,j) * mat.determinanteComSwitch(matAux,ordem-1));
        }
        return somaDet;
    }
    public int Cofator(int indice, int indice2){

        int resposta = ((indice+indice2)%2 == 0) ? 1 : -1;

        return resposta;
    }


    public int colunaFixa_detLaplaceOtimizado(Matriz mat, int ordem, int indice){
        Matriz matAux = new Matriz(ordem-1,ordem-1);
        int somaDet = 0;

        for(int i = 0; i < ordem; i++){
            this.copiaMatriz(mat,matAux,i, indice);
            if(mat.getElemento(i,indice) == 0){
            	somaDet += 0;
            }else{
            	somaDet += (Cofator(i,indice) * mat.getElemento(i,indice) * mat.detRecursivoOtimizado(matAux,ordem-1));
            }
        }

        return somaDet;
    }


    public int linhaFixa_detLaplaceOtimizado(Matriz mat, int ordem, int indice){
        Matriz matAux = new Matriz(ordem-1,ordem-1);
        int somaDet = 0;

        for(int j = 0; j < ordem; j++){
            this.copiaMatriz(mat,matAux,indice,j);
            if(mat.getElemento(indice,j) == 0){
            	somaDet += 0;
            }else{
            	somaDet += (Cofator(indice,j) * mat.getElemento(indice,j) * mat.detRecursivoOtimizado(matAux,ordem-1));
            }

        }

        return somaDet;
    }

        public int detLaplaceOtimizado(Matriz mat, int ordem){
        int indice = 0;
        int resposta = 0;

        if((mat.zerosNaLinha() != 0) || (mat.zerosNaColuna() != 0)){
            if(mat.zerosNaLinha() >= mat.zerosNaColuna()){
                indice = mat.indiceLinha_MaisZeros();
                resposta = mat.linhaFixa_detLaplaceOtimizado(mat,ordem,indice);

            }else if(mat.zerosNaColuna() > mat.zerosNaLinha()){
                indice = mat.ColunaComMaisZeros();
                resposta = mat.colunaFixa_detLaplaceOtimizado(mat,ordem,indice);

            }
        }else if((mat.zerosNaLinha() == 0) && (mat.zerosNaColuna() == 0)){
            resposta = mat.detLaplace(mat,ordem);
        }
        return resposta;
    }
    public int zerosNaLinha(){
        int contZ, valor, contMaior = 0;

        for(int i = 0; i < this.getLinhas(); i++){
            contZ = 0;
            for(int j = 0; j < this.getColunas(); j++){
                valor = this.getElemento(i,j);
                if(valor == 0){
                    contZ++;
                }
            }
            if(contMaior < contZ){
                contMaior = contZ;
            }
        }
        return contMaior;
    }

    public int zerosNaColuna(){
        int contZ, valor,  contMaior = 0;

        for(int j = 0; j < this.getColunas(); j++){
            contZ = 0;
            for(int i = 0; i < this.getLinhas(); i++){
                valor = this.getElemento(i,j);
                if(valor == 0){
                    contZ++;
                }
            }
            if(contMaior < contZ){
                contMaior = contZ;
            }
        }
        return contMaior;
    }
       public int indiceLinha_MaisZeros(){
        int contZ, valor, contMaior = 0, indice = 0;

        for(int i = 0; i < this.getLinhas(); i++){
            contZ = 0;
            for(int j = 0; j < this.getColunas(); j++){
                valor = this.getElemento(i,j);
                if(valor == 0){
                    contZ++;
                }
            }
            if(contMaior < contZ){
                contMaior = contZ;
                indice = i;
            }
        }
        return indice;
    }


    public int ColunaComMaisZeros(){
        int colunaZ, valor, aux, indice = 0;
        aux = 0;
        for(int j = 0; j < this.getColunas(); j++){
            colunaZ = 0;
            for(int i = 0; i < this.getLinhas(); i++){
                valor = this.getElemento(i,j);
                if(valor == 0){
                   colunaZ++;
                }
            }
            if(aux < colunaZ){
                aux = colunaZ;
                indice = j;
            }
        }
        return indice;
    }


}
public class mainMatriz{
    public static void main(String[] args){
	Matriz mat = new Matriz(4,4); //ordem da matriz

	mat.inicializaRandomico();
        mat.imprimidorMatriz();

	long startTime = System.nanoTime();
	mat.determinante();
	long endTime = System.nanoTime();
	long TempoNaoOtimizado = endTime - startTime;
        double  totalMilisegundosNaoOtimizado=TempoNaoOtimizado/1000000.0;
        long startTime2 = System.nanoTime();
	System.out.println();
	System.out.printf("Determinante = %d\n",+mat.detOtimizado());

	long endTime2 = System.nanoTime();
	long TempoOtimizado = endTime2 - startTime2;
        double  totalMilisegundosOtimizado=TempoOtimizado/1000000.0;
	System.out.println();
	System.out.printf("Tempo nao otimizado = %d nanossegundos\n",TempoNaoOtimizado);
        System.out.printf("Tempo nao otimizado = %f milissegundos\n",totalMilisegundosNaoOtimizado);
	System.out.println();
        System.out.printf("Tempo com otimizacao= %d nanossegundos\n",TempoOtimizado);
        System.out.printf("Tempo com otimizado = %f milissegundos\n",totalMilisegundosOtimizado);

	}
}